문제

[백준] 적록색약 (Gold 5)

요약

  • R(빨강), G(초록), B(파랑) 으로 이루어진 격자가 주어진다.
  • 적록색약을 가진 이는 R과 G를 구분하지 않는다.
  • 적록색약을 가진 이와 가지지 않은 이가 보는 격자의 구역 개수를 반환하라.

분류

  • DFS
  • 큐

풀이

1. DFS

  • 큐를 이용한 DFS
  • 적(R) 혹은 록(R)에 해당하는 색이면 X로 바꿔가며, DFS 탐색을 진행하여, 적록색약을 가지지 않은 사람이 보는 격자의 구역 개수를 구한다.
  • 위 과정이 끝나면 격자에는 X 와 B만 남는다. 다시 DFS 탐색을 진행하여, 적록색약을 가진 사람이 보는 격자의 구역 개수를 구한다.


import sys
input = sys.stdin.readline

n = int(input())
arr = [
    list(input().rstrip()) for _ in range(n)
]
visit = [
    [True for _ in range(n)] for _ in range(n)
]

dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]  # 북동남서

cnt = 0
D_cnt = 0


def dfs(y, x, prev):
    stack = [(y, x)]
    visit[y][x] = False
    if arr[y][x] == 'R' or arr[y][x] == 'G':
        arr[y][x] = 'X'
    while stack:
        y, x = stack.pop()

        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            if ny >= 0 and ny < n and nx >= 0 and nx < n and visit[ny][nx] and arr[ny][nx] == prev:
                if arr[ny][nx] == 'R' or arr[ny][nx] == 'G':
                    arr[ny][nx] = 'X'
                stack.append((ny, nx))
                visit[ny][nx] = False


for r in range(n):
    for c in range(n):
        if visit[r][c]:
            dfs(r, c, arr[r][c])
            cnt += 1

visit = [
    [True for _ in range(n)] for _ in range(n)
]


for r in range(n):
    for c in range(n):
        if visit[r][c]:
            dfs(r, c, arr[r][c])
            D_cnt += 1

print(cnt, D_cnt)