#357 백준 파이썬 [10026] 적록색약 - BFS

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

 

SOLUTION

BFS(너비우선탐색 그래프)를 통해 쉽게 해결 가능하다. (참조: https://claude-u.tistory.com/211)

 

BFS를 기본인 상태에서 한 번,

G를 R로 바꾼 상태에서 한 번 실행시켜준다.

PYTHON CODE

from collections import deque #큐를 빨리 돌리기위함

#BFS함수 정의
def bfs(i, j):
    queue = deque()
    queue.append([i, j])
    color = grid[i][j] #하나의 컬러만
    
    while queue:
        [i, j] = queue.popleft()
        visited[i][j] = True
        
        if i + 1 < N and [i+1, j] not in queue and visited[i+1][j] == False and grid[i+1][j] == color:
            queue.append([i+1, j])
        if i - 1 >= 0 and [i-1, j] not in queue and visited[i-1][j] == False and grid[i-1][j] == color:
            queue.append([i-1, j])
        if j + 1 < N and [i, j+1] not in queue and visited[i][j+1] == False and grid[i][j+1] == color:
            queue.append([i, j+1])
        if j - 1 >= 0 and [i, j-1] not in queue and visited[i][j-1] == False and grid[i][j-1] == color:
            queue.append([i, j-1])
            
    return #아무것도 리턴해주지 않아도됨(실행 자체로 의미)


#인풋
N = int(input())
grid = [input() for _ in range(N)] #RGB 인풋

visited = [[False for _ in range(N)] for _ in range(N)] #방문 했는가
answer_1 = 0 #몇 구역
for i in range(N):
    for j in range(N):
        if not visited[i][j]: #방문 안했을 시
            bfs(i, j) #방문
            answer_1 += 1 #그룹 + 1

#모든 G를 R로 바꾸어줌
for i in range(N):
    for j in range(N):
        if grid[i][j] == 'G':
            grid[i][j] = 'R'

visited = [[False for _ in range(N)] for _ in range(N)]
answer_2 = 0
for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            bfs(i, j)
            answer_2 += 1
            
print(answer_1, answer_2)