[백준/파이썬] 10026번

📍백준 10026번 문제

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

코드

from collections import deque
import sys
input = sys.stdin.readline
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs1(graph, a, b):
    queue = deque()
    queue.append((a, b))
    temp = graph[a][b]
    if temp == 'B':
        graph[a][b] = 'X'
    else:
        graph[a][b] = 'Y'
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if graph[nx][ny] == temp:
                if graph[nx][ny] == 'B':
                    graph[nx][ny] = 'X'
                else:
                    graph[nx][ny] = 'Y'
                queue.append((nx, ny))


def bfs2(graph, a, b):
    queue = deque()
    queue.append((a, b))
    temp = graph[a][b]
    graph[a][b] = 'A'
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if graph[nx][ny] == temp:
                graph[nx][ny] = 'A'
                queue.append((nx, ny))


n = int(input())
cnt1 = 0
cnt2 = 0
graph = [list(map(str, input().rstrip('\n'))) for _ in range(n)]
for i in range(n):
    for j in range(n):
        if graph[i][j] == 'R' or graph[i][j] == 'G' or graph[i][j] == 'B':
            bfs1(graph, i, j)
            cnt1 += 1


for i in range(n):
    for j in range(n):
        if graph[i][j] != 'A':
            bfs2(graph, i, j)
            cnt2 += 1

print(cnt1, cnt2)

풀이

BFS로 구하면 된다.
우선 적록색약이 아닌 사람의 구역의 수를 구한다.
이때 방문한 구역은 방문했다는 표시로 B는 X로, R과 G는 Y로 바꿔준다.
R과 G의 값이 같은 이유는 적록색약인 사람은 R과 G를 구분하지 못하기 때문이다.