[백준] 10026 - 적록색약(BFS)

JunHwa Park 2020. 10. 22. 16:49

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

10026번: 적록색약

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)

www.acmicpc.net

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
33
34
35
36
37
38
39
40
41
42
43
44
45

from collections import deque
 
dd = ((0, 1), (1, 0), (-1, 0), (0, -1))
n = int(input())
graph = [[c for c in input()] for _ in range(n)]
visited = [[False] * n for _ in range(n)]
answer = [0, 0]
q = deque()
 
# 일반인
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            color = graph[i][j]
            answer[0] += 1
            q.append((i, j))
            visited[i][j] = True
            while q:
                y, x = q.popleft()
                for d in range(4):
                    dy, dx = y + dd[d][0], x + dd[d][1]
                    if 0 <= dy < n and 0 <= dx < n and not visited[dy][dx] and color == graph[dy][dx]:
                        visited[dy][dx] = True
                        q.append((dy, dx))
# 적록색약
visited = [[False] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            color = graph[i][j]
            answer[1] += 1
            q.append((i, j))
            visited[i][j] = True
            while q:
                y, x = q.popleft()
                for d in range(4):
                    dy, dx = y + dd[d][0], x + dd[d][1]
                    if 0 <= dy < n and 0 <= dx < n and not visited[dy][dx]:
                        if color == 'B' and color == graph[dy][dx]:
                            visited[dy][dx] = True
                            q.append((dy, dx))
                        elif color != 'B' and graph[dy][dx] != 'B':
                            visited[dy][dx] = True
                            q.append((dy, dx))
print(answer[0], answer[1])
Colored by Color Scripter

cs

bfs로 돌면서 풀면 된다.

주의할 점은, 큐에 넣는 순간 visited를 설정해야 한다는 것.