백준: 10026 적록색약

문제

10026번: 적록색약

 

문제 풀이

 그래프에 `R`, `G`, `B` 세 가지 색깔이 주어지는데, 적록색약의 경우 `G`를 구분할 수 없다. 이에, 그래프의 영역을 탐색하되, 색약이지 않는 사람이 구분하는 영역과 적록색약인 사람이 구분하는 영역을 출력하는 문제이다. 앞서 다룬 단지 번호 붙이기와 동일한 로직으로 풀면 된다. 다른 점은 한번 그래프를 탐색하고, `G`인 경우에는 `R`로 바꾸어 다시 한번 탐색하여야 한다. 또한, 단지의 수를 세는 것이 아닌 영역의 수를 센다는 것이 다르다.

 

코드

from sys import stdin
from collections import deque


def visitable(x, y):
    return 0 <= x < n and 0 <= y < n and not visited[x][y]


def bfs(start, cur_color):
    q = deque([start])
    dirs = ((1, 0), (-1, 0), (0, -1), (0, 1))

    while q:
        x, y = q.popleft()

        for dx, dy in dirs:
            next_x, next_y = x + dx, y + dy
            if visitable(next_x, next_y) and graph[next_x][next_y] == cur_color:
                visited[next_x][next_y] = True
                q.append([next_x, next_y])


if __name__ == '__main__':
    n = int(stdin.readline())
    graph = [list(stdin.readline().rstrip()) for _ in range(n)]
    answer = [0, 0]

    for idx in range(2):
        visited = [[False] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                if not visited[i][j]:
                    visited[i][j] = True
                    bfs([i, j], graph[i][j])
                    answer[idx] += 1
        graph = [['R' if graph[i][j] == 'G' else graph[i][j] for i in range(n)] for j in range(n)]

    print(answer[0], answer[1])