문제 링크
난이도 : Gold 5
BFS를 적록 색약인 경우와 그렇지 않은 경우를 독립적으로 2번 수행하면 된다.
BFS 를 2번 따로 하면 시간 초과 날까?
그룹화를 해서 한번에 안될까?
완전히 다른 맵을 따로 BFS를 하면
시간 복잡도 O(N^2) 동일하다
NxN 행렬을 독립적으로 두번 탐색하는 BFS를 자연스럽게 하지 않으려 하는 것 같다. 이 문제는 독립적으로 BFS 탐색을 두번하면 아주 간단하게 해결 가능한데, 무의식적으로 한번에 하려는 생각을 해보게 된다.. ㅠ
시간 복잡도 NxN 행렬을 독립적으로 2번 탐색시 O(N^2)으로 동일하다.
오히려, 한번에 하려는 생각이 독이 될 수 있다. 조심하자
그리고, 한 번에 적록 색약 탐색 방식도 당연히 가능할 것 같다. 지금은 아이디어만 적어 놓고 넘어가자!
red, green, blue, red-green 좌표를 따로 SET 객체로 중복 없이 저장 후, blue 연결 체크로 먼저 BFS후, red, green, red-green 순으로 탐색
from collections import deque
N = int(input())
board = [ list(input()) for _ in range(N) ]
board2 = [ row[:] for row in board ]
vis = [[False]*N for _ in range(N)]
dir = [ [0,1], [0,-1], [1,0], [-1,0] ]
ans = [0, 0]
def BFS (i, j, arr) :
q = deque()
q.append([i , j, arr[i][j]])
vis[i][j] = True
while q :
curR, curC, curColor = q.popleft()
for r, c in dir :
nxtR = curR + r
nxtC = curC + c
if nxtR < 0 or nxtC < 0 or nxtR >= N or nxtC >= N or vis[nxtR][nxtC] : continue
if curColor == arr[nxtR][nxtC] :
vis[nxtR][nxtC] = True
q.append([ nxtR, nxtC, arr[nxtR][nxtC] ])
return 1
for i in range(N) :
for j in range(N) :
if board[i][j] == 'G' : board2[i][j] = 'R'
if vis[i][j] : continue
ans[0] += BFS(i,j, board)
vis = [[False]*N for _ in range(N)]
for a in range(N) :
for b in range(N) :
if vis[a][b] : continue
ans[1] += BFS(a,b, board2)
print(*ans)