BFS [G5] 적록색약

문제 링크
난이도 : Gold 5

간단 솔루션

BFS를 적록 색약인 경우와 그렇지 않은 경우를 독립적으로 2번 수행하면 된다.

Issue

BFS 를 2번 따로 하면 시간 초과 날까?
그룹화를 해서 한번에 안될까?

Soln

완전히 다른 맵을 따로 BFS를 하면
시간 복잡도 O(N^2) 동일하다

Detail

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)