[baekjoon] 백준 10026번 : 적록색약 (by python) bfs dfs

https://www.acmicpc.net/problem/10026

10026번: 적록색약

 

정답 code

-bfs활용

#적록색약
from collections import deque
import sys
input = sys.stdin.readline
dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(x,y):
    q.append([x,y])
    visit[x][y] = cnt
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if 0<=nx< n and 0<=ny< n:
                if color[nx][ny] == color[x][y] and visit[nx][ny] == 0:
                    q.append([nx,ny])
                    visit[nx][ny] = 1
                
n = int(input())
color = [list(input()) for _ in range(n)]
visit = [[0]*n for _ in range(n)]
q = deque()

cnt = 0
for i in range(n):
    for j in range(n):
        if visit[i][j] == 0:
            bfs(i,j)
            cnt += 1
print(cnt,end=' ')

for i in range(n):
    for j in range(n):
        if color[i][j] == 'R':
            color[i][j] = 'G'
    
visit = [[0]*n for _ in range(n)]

cnt = 0
for i in range(n):
    for j in range(n):
        if visit[i][j] == 0:
            bfs(i,j)
            cnt += 1
        
print(cnt)

 

solution

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 구분하여 출력해야하는데 

적록색약인 사람이 봤을때 구역수는 R 과 G를 합하여만든 구역수로 출력하면 된다.

 

먼저 방문하지 않은 색깔에대해 bfs함수를 실행해 구역수를 구해주고 

R을 G로 변환후 방문 함수를 초기화 시키고 구역수를 구해준다.