[백준] 10026번 적록색맹

아이디어

1) BFS로 구현

2개의 그래프를 따로 생성한다.

적록색맹 아닌 사람 --> 입력한 그래프 그대로 사용한다.

적록색맹인 사람 --> G를 R로 replace한 그래프를 사용한다. (R과 G를 같은것으로 취급하기때문)

visited 리스트를 만들어 방문 여부를 체크한다.

그래프를 반복문으로 돌며 방문하지 않은 노드에 대해 BFS탐색을 수행한다.

해결

1) BFS 로 구현 

DFS로 구현했을때의 런타임에러(RecursionError)를 피할 수 있다.

def bfs(graph,x,y):
    q=deque()
    q.append((x,y))
    visited[x][y]=True
    while q:
        x,y=q.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx<0 or ny<0 or nx>=n or ny>=n:
                continue
            if visited[nx][ny]==True:  #이미 방문했다면 아무것도 하지않고 넘어감
                continue
            elif graph[nx][ny]==graph[x][y]: #아직 방문안했다면 방문처리,큐에넣기
                q.append((nx,ny))
                visited[nx][ny]=True #방문처리

    
from collections import deque
import sys
input = sys.stdin.readline
dx=[-1,1,0,0] #좌,우
dy=[0,0,-1,1] #상,하
n=int(input().rstrip())
visited=[[False]*n for _ in range(n)]
graph=[]
graph2=[]
cnt=0
cnt_bl=0

for i in range(n):
    string=input().rstrip()
    graph.append(list(string))            #그래프 2차원리스트로 표현
    graph2.append(list(string.replace("G","R")))

for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            bfs(graph,i,j)
            cnt+=1

visited=[[False]*n for _ in range(n)]       #다시 visited 방문여부 확인할 리스트 초기화
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            bfs(graph2,i,j)
            cnt_bl+=1
            
print(cnt, cnt_bl)