[백준/Python] 10026_적록색약

문제

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

10026번: 적록색약

풀이

이 문제는 bfs를 이용해서 풉니다.

입력받은 2차원 matrix와 matrix에서 G을 R로 바꾼 fixed_matrix 두 개의 배열을 사용합니다.

매개변수로 입력받은 matrix의 RGB 구역의 수를 구하는 count_RGB 함수를 선언하여 답을 구합니다.

코드

import sys
from collections import deque


def count_RGB(graph):
    result = 0
    visited = [[False] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                q = deque([(i, j)])
                visited[i][j] = True
                current_color = graph[i][j]
                result += 1
                while q:
                    r, c = q.popleft()
                    for k in range(4):
                        nr = r + dy[k]
                        nc = c + dx[k]
                        if 0 <= nr < n and 0 <= nc < n:
                            if not visited[nr][nc] and graph[nr][nc] == current_color:
                                q.append((nr, nc))
                                visited[nr][nc] = True
    return result


n = int(sys.stdin.readline().rstrip())
matrix = []
for _ in range(n):
    matrix.append(list(sys.stdin.readline().rstrip()))
fixed_matrix = [[] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if matrix[i][j] == 'R' or matrix[i][j] == 'G':
            fixed_matrix[i].append('R')
        else:
            fixed_matrix[i].append('B')

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

print(count_RGB(matrix), end=' ')
print(count_RGB(fixed_matrix))