[bfs/백준] 10026번 : 적록색약

 - 문제 : https://www.acmicpc.net/problem/10026

 

스스로 푼 문제다 ! Gold Level5 문제 

처음에는 적록색약이 아닌 사람에 대한 bfs와 적록색약인 사람에 대한 bfs를 따로 만들어줘야하나 고민이 됐다. 

일단 적록색약이 아닌 경우는 그동안 해온 bfs로 하면 되는데, 문제는 적록색약인 사람은 R과 G이 같게 인식돼 R에서 G로 갈 수도, G에서 R로 갈 수도 있는데 이를 어떻게 구현해야할지 몰랐다. 

 

일단 되는대로 bfs 두개 만들어서 돌렸는데 틀렸다. 그래서 갑자기 생각난게 적록색약 아닌 경우 진행한 다음에 R과 G의 값을 하나로 치환한뒤 같은 bfs 돌리면 갯수 나오겠다 싶어서 그렇게 돌렸더니 정답이 떴다. 

 

처음에 풀었을 때는 엄청 헤맸는데, 두번째 풀이 때는 스스로 풀어서 뿌듯하다

 

- 정답 풀이 :

from collections import deque
n=int(input())
data=[]
for _ in range(n):
    data.append(list(input()))
dx=[-1,1,0,0]
dy=[0,0,-1,1]
one,two=0,0

def bfs(x,y,letter):
    queue=deque()
    queue.append((x,y))
    while queue:
        x,y=queue.popleft()
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<n and 0<=ny<n:
                if not visit[nx][ny] and data[nx][ny]==letter:
                    visit[nx][ny]=1
                    queue.append((nx,ny))
                    
visit=[[0]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if not visit[i][j]:
            bfs(i,j,data[i][j])
            one+=1

#적록색약은 적색과 녹색이 같게 보이므로, 둘을 같은 문자로 치환해준다            
for i in range(n):
    for j in range(n):
        if data[i][j]=='R' or data[i][j]=='G':
            data[i][j]='K'
            
visit=[[0]*n for _ in range(n)]            
for i in range(n):
    for j in range(n):
        if not visit[i][j] :
            bfs(i,j,data[i][j])
            two+=1
            
print(one,two)