문제
접근
두 가지 방법으로 접근할 수 있을 것 같다.
Board를 한 개만 두고 일반인과 색약인 사람에 대해 각각 visit 배열을 두고 진행하는 방법.
혹은, visit를 사용하지 않고, 일반인과 색약인 사람에 대해 각각 Board를 두고 Board에 visit을 체크하는 방법.
후자가 더 간단해보여서 후자로 구현하였다.
여태 풀었던 BFS는 보통 벽같은게 존재했지만, 여기서는 벽은 없고 각 지점의 값이 같은 곳끼리 영역을 이루는 방식이다.
인접한 지역의 값이 시작 지역의 값과 같은지만 체크하며 BFS를 수행하면 된다.
코드
- 파이썬 코드
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
46
47
48
49
50
51
52
from collections import deque
def bfs(sx, sy, board):
dx = [0,0,1,-1]
dy = [1,-1,0,0]
q = deque()
q.append((sx,sy))
val = board[sy][sx]
board[sy][sx] = 0
while q:
nowx, nowy = q.popleft()
for x, y in zip(dx, dy):
nx = nowx + x
ny = nowy + y
if nx < 0 or nx >= n or ny < 0 or ny >= n:
continue
if board[ny][nx] == val:
board[ny][nx] = 0
q.append((nx,ny))
return board
n = int(input())
normalBoard = []
unnormalBoard = []
for i in range(n):
tmp = input()
normalRow = []
unnormalRow = []
for item in tmp:
if item == 'R':
normalRow.append(1)
unnormalRow.append(1)
elif item == 'G':
normalRow.append(2)
unnormalRow.append(1)
else:
normalRow.append(3)
unnormalRow.append(2)
normalBoard.append(normalRow)
unnormalBoard.append(unnormalRow)
normal = 0
unnormal = 0
for i in range(n):
for j in range(n):
if normalBoard[i][j] != 0:
bfs(j,i,normalBoard)
normal += 1
if unnormalBoard[i][j] != 0:
bfs(j,i,unnormalBoard)
unnormal += 1
print(normal, unnormal)