BOJ-10026 적록색약

https://www.acmicpc.net/problem/10026

문제 소개

R(빨강), G(초록), B(파랑)으로 이루어진 그림의 정보가 주어진다. 그리고 같은 색상이 상하좌우로 인접해 있는 경우 같은 구역이라고 정의하였다.

그림을 적록색약인 사람과 적록색약이 아닌 사람이 봤을 때 몇 개의 구역으로 나뉘어지는지 출력한다.

적록색약인 사람을 빨강과 초록의 차이를 거의 느끼지 못하며, 문제에서는 같은 색상으로 인식한다고 가정하였다.

문제 풀이

인접한 같은 색상을 BFS로 탐색하도록 하였다.

함수 bfs는 탐색을 시작하는 좌표인 x와 y 말고도 시작 좌표의 색상인 c와 적록색상의 여부를 나타내는 bool형 변수인 weakness를 매개변수로 갖는다.

bfs는 weakness와 c를 토대로 인접한 색상 중 어떤 색상을 같은 구역으로 간주할 지를 변수 target에 저장한다.

만약 적록색약인 동시에 색상이 빨강 또는 초록이라면 target의 값은 ('R', 'G')이며, 그 외의 경우는 c만을 가진다.

target의 지정 후에는 인접한 색상에 대해 bfs를 진행하게 된다.

적록색약이 아닌 사람이 인식한 구역 수와 적록색약인 사람이 인식한 구역의 수는 각각 cnt0, cnt1로 나타내었다.

두 변수는 각각 0으로 초기화된 이후, weakness로 구분되는 각각의 bfs수행을 통해 증가한다.

마지막으로 누적된 cnt0과 cnt1를 출력한다.

코드

from sys import stdin
from collections import deque
input = lambda: stdin.readline().rstrip()

# 좌, 상, 우, 하 순서
d = [(0, -1), (-1, 0), (0, 1), (1, 0)]


# bfs 수행
def bfs(x, y, c, weakness: bool):
    queue = deque([(x, y)])
    visited[x][y] = True

    # target 색상 설정
    if weakness and c in ('R', 'G'):
        target = ('R', 'G')
    else:
        target = tuple(c)

    while queue:
        t = queue.popleft()
        for i in range(4):
            nx, ny = t[0] + d[i][0], t[1] + d[i][1]
            # 좌표가 유효한 범위에 속하면서 아직 방문하지 않았고 target에 포함된 경우
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and arr[nx][ny] in target:
                queue.append((nx, ny))
                visited[nx][ny] = True


n = int(input())
arr = [list(input()) for _ in range(n)]
visited = [[False] * n for _ in range(n)]

cnt0, cnt1 = 0, 0
# 적록색약이 아닌 경우
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            bfs(i, j, arr[i][j], False)
            cnt0 += 1

# visited 다시 초기화
visited = [[False] * n for _ in range(n)]

# 적록색약인 경우
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            bfs(i, j, arr[i][j], True)
            cnt1 += 1

print(cnt0, cnt1)