적록 색약 (골드 5)

적록색약 성공다국어

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

59378

34155

26017

56.505%

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

출력

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

예제 입력 1 복사

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

예제 출력 1 복사

4 3

---

• 접근 방법

 

이번에는 참고자료 없이 손쉽게 문제를 풀었다.

 

일반인의 색 구분과 색맹 환자의 색 구분을 어떻게 다르게 구분할지 고민해보았다.

 

결론은 적록 색약이 인지하지 못하는 색을 하나로 통일시키는 방법으로 쉽게 구현했다.

---

• 구현 및 코드 설명

 

결국 BFS 방법으로 visited 리스트로 방문 여부를 체크하며 그래프 순회 하는 방식이 동일하고

 

그래프 순환이 이루어질 때 count 함수를 증가시켜 색구분의 개수를 구한다.

 

그리고 bfs 파라미터로 해당 색 만 탐색하도록 구현하도록 변형하였다.

 

• 입력 처리 및 visited 리스트 초기화

from collections import deque

N = int(input())

graph = [[] for _ in range(N)]

visited = [[False] * N for _ in range(N)]

 

이전 코드와 마찬가지로 2차원 리스트를 묵시적 그래프로 입출력 처리를 해주었다.

 

• count_color 함수 구현

색 카운트를 구하는 함수 count_color

 

확실히 함수 부분 구현능력이 향상됨을 느꼈다.

 

파라미터를 추가하여 탐색 타깃을 바꾸어주는 간단한 변형이 이루어졌고

 

이후 색약자를 위해 임의의 문자 "P"의 조건 또한 추가해 주었다.

 

 

• BFS 구현

BFS

BFS 함수에서는 target 파라미터를 추가하여 탐색하는 조건을 변화시켜 준 점 말고는 이전 문제에서 활용한 BFS함수와 특별히 다른 점이 없다. 

일반인의 count 출력

일반 입력으로 받은 그래프 (R, G, B)로 이루어진 graph를 파라미터를 넘겨주어 count 값을 구한 후 출력한다.

 

• 적록 색맹

적록 색맹이 인지할 graph 초기화 방법

 

이 문제의 핵심인 적록 색약을 어떻게 표현할 수 있을까 생각하였고, 적록 색약은 적색과 녹색을 하나로 인식하기 때문에 G와 R을 "P" 문자열로 대체해주었다. 

 

이후 다시 탐색하기 위해 visited와 count를 초기값으로 다시 초기화하였다.

 

이후 count를 출력하면 코드가 완성된다.

 

• 출력값

최종 결과

•  전체 코드

from collections import deque

N = int(input())

graph = [[] for _ in range(N)]

visited = [[False] * N for _ in range(N)]

for i in range(N):

    graph[i] = list(input())

dx = [0, 0, -1, 1]

dy = [1, -1, 0, 0]

q = deque()

count = 0

def bfs(r, c, target):

    global count

    count += 1

    q.append((r, c))

    visited[r][c] = True

    while q:

        cur_r, cur_c = q.popleft()

        for i in range(4):

            next_r = cur_r + dy[i]

            next_c = cur_c + dx[i]

            if 0 <= next_r < N and 0 <= next_c < N:

                if graph[next_r][next_c] == target and not visited[next_r][next_c]:

                    q.append((next_r, next_c))

                    visited[next_r][next_c] = True

    return visited

def count_color(graph):

    for i in range(N):

        for j in range(N):

            if graph[i][j] == "R" and not visited[i][j]:

                target = "R"

                bfs(i, j, target)

            if graph[i][j] == "G" and not visited[i][j]:

                target = "G"

                bfs(i, j, target)

            if graph[i][j] == "B" and not visited[i][j]:

                target = "B"

                bfs(i, j, target)

            if graph[i][j] == "P" and not visited[i][j]:

                target = "P"

                bfs(i, j, target)

    return count

count_color(graph)

print(count, end=" ")

for i in range(N):

    for j in range(N):

        if graph[i][j] == "G" or graph[i][j] == "R":

            graph[i][j] = "P"

visited = [[False] * N for _ in range(N)]

count = 0

count_color(graph)

print(count)

 

 

• 느낀 점 및 배운 점

 

이번 문제는 토마토 문제와 다르게 특별히 예외 처리하는 부분이 없어 쉽게 풀렸던 것 같다.

 

내 풀이를 정리하며 생각해 낸 것이 굳이 P 문자열이 아닌 하나의 문자열 G 혹은 R로 통일시키는 방법이 더 유용했을 것이다.

 

이후 다른 사람의 풀이를 통해 코드 견문을 넓히는 시간을 가져야겠다.