[백준] 10026 적록색약 / BFS / Python 골5

BFS 한번 풀면 BFS만 계속 푼다는 루머를 안믿었는데

간단한 BFS는 그냥 바로 풀이가 눈에 보이고... 손에 한번만 익히면 다 풀 수 있어서...

이것도 그냥 보자마자 바로 짜서 푼듯 2~30분 정도 걸린 듯?

 

적록색약이 아닌 경우 (no)

적록색약인 경우(yes)

로 함수를 나누고

 

이중 for문으로 그림 요소를 모두 탐색할 때

visited 배열을 적록색약인 경우 or not 각각 2개 둬서

탐색되지 않은 원소만 bfs로 진입한다

 

적록색약이 아닌 경우는 현재 입력된 문자와 같은 경우만 q에 append하고,

적록색약인 경우에는 현재 입력된 문자가 B인 경우에는 B만 q에 append, R or G인 경우에는 R or G를 모두 q에 append한다

 

이렇게 bfs를 술술 짰더니 바로 맞았습니다가 떴다

 

 

 

from collections import deque
n = int(input())

color = [list(map(str,input().strip())) for _ in range(n)]

# R과 G의 차이 거의 못느낌

dx=[0,0,1,-1]
dy=[1,-1,0,0]
def no(i,j, char):
    q=deque()
    q.append([i,j])
    visited[i][j]=True
    while q:
        y,x = q.popleft()
        visited[y][x]=True
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<n and 0<=ny<n and not visited[ny][nx] and color[ny][nx]==char:
                visited[ny][nx]=True
                q.append([ny,nx])

def yes(i,j,char):
    q=deque()
    q.append([i,j])
    visited_y[i][j]=True
    while q:
        y,x = q.popleft()
        visited_y[y][x]=True
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<n and 0<=ny<n and not visited_y[ny][nx]:
                if char=='B' and color[ny][nx]=='B':
                    visited_y[ny][nx]=True
                    q.append([ny,nx])
                elif (char=='G' or char=='R') and (color[ny][nx]=='G' or color[ny][nx]=='R'):
                    visited_y[ny][nx]=True
                    q.append([ny,nx])


cnt_n=0
cnt_y=0
visited=[[False for _ in range(n)] for _ in range(n)]
visited_y = [[False for _ in range(n)] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            no(i,j,color[i][j])
            cnt_n+=1
        if not visited_y[i][j]:
            yes(i,j,color[i][j])
            cnt_y+=1

print(cnt_n, cnt_y)