[Algorithm] 백준 10026 적록색약 | 파이썬 BFS

※ 10026 적록색약

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

문제 해결 TIP

유기농 배추 문제와 같이 처음에 DFS로 풀다가 RecursionError에 걸려서 BFS로 바꾸었다. 적록색약인 것과 아닌 것의 그래프를 애초에 따로 저장하여 bfs로 돌려주었다.

 

전체 코드

from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

N = int(input())
graph = [] #적록색약이 아닌 그래프
for i in range(N):
    graph.append(list(map(str,input())))

new_graph = [row[:] for row in graph]  #적록색약이 보는 그래프
# 새로운 그래프에서 'G' 값을 'R'로 바꾸기
for i in range(len(new_graph)):
    for j in range(len(new_graph[i])):
        if new_graph[i][j] == 'G':
            new_graph[i][j] = 'R'

def bfs(graph,x, y,color):
    queue = deque()
    queue.append((x, y))
    graph[x][y] = 0
    while queue:
        x, y = queue.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 graph[nx][ny] == color:
                queue.append((nx, ny))
                graph[nx][ny] = 0
    return True

count = 0
no_count = 0
for i in range(N):
    for j in range(N):
        if graph[i][j] in ('R', 'G', 'B'):
            if bfs(graph, i, j, graph[i][j]):
                count += 1

for i in range(N):
    for j in range(N):
        if new_graph[i][j] in ('R', 'B'):
            if bfs(new_graph, i, j, new_graph[i][j]):
                no_count += 1
print(count)
print(no_count)