문제 링크

문제 해설

Idea

  • 모든 방문하지 않은 칸에 대해 BFS 탐색하면서 같은 구역을 방문
  • 적록색약의 경우 R과 G를 같은 구역으로 판단하고 탐색
  • 각각의 경우에 대한 BFS 호출 횟수를 서로 다른 구역의 수로 판단하여 출력

Time Complexity

  • BFS: O(N^2) = 10,000

Data Size

  • N: 1 <= int <= 100

해설 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

from collections import deque
import sys
input = sys.stdin.readline

N = int(input())
grid = [list(input().strip()) for _ in range(N)]
visited = [[[False] * N for _ in range(N)] for _ in range(2)]
answer = [0, 0]

def bfs(start, visited, st):
    queue = deque([start])
    dy = [0,1,0,-1]
    dx = [-1,0,1,0]

    while queue:
        y,x = queue.popleft()
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0<=ny<N and 0<=nx<N and not visited[ny][nx]:
                if st[grid[y][x]] == st[grid[ny][nx]]:
                    queue.append((ny,nx))
                    visited[ny][nx] = True
    return 1

for i in range(N):
    for j in range(N):
        if not visited[0][i][j]:
            answer[0] += bfs((i,j), visited[0], {'R':0,'G':1,'B':2})
        if not visited[1][i][j]:
            answer[1] += bfs((i,j), visited[1], {'R':0,'G':0,'B':2})

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