[Python] 백준 10026번 - 적록색약

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

10026번: 적록색약

 

골드라서 좀 겁먹었었는데 무난한 그래프 문제였다.

그리드에 색 입력 받을 때 'R', 'R', 'R', 'B', 'B' 이런 식으로 되어야 하는데

자꾸 'RRRBB' 이렇게 받아져서 그 부분 조금 헤맸다.

 

 

색약이 아닌 경우를 먼저 구하고,

'R'을 'G'로 바꾼 후 색약인 경우를 구한다. ('G' -> 'R'도 가능)

이때 visited 초기화 해주어야 하는 것 잊지 말기.

 

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def bfs(x, y):
    visited[x][y] = 1
    q = deque()
    q.append((x, y))
    while q:
        x, y = q.popleft()
        dxdy = [(0, -1), (0, 1), (-1, 0), (1, 0)]
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if -1 < nx < n and -1 < ny < n:
                if grid[nx][ny] == grid[x][y] and not visited[nx][ny]:
                    visited[nx][ny] = 1
                    q.append((nx, ny))

n = int(input())
grid = [list(map(str, input().strip())) for _ in range(n)]
visited = [[0 for _ in range(n)] for _ in range(n)]

ncw = 0 #색약 x
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            bfs(i, j)
            ncw += 1
print(ncw, end=' ')

cw = 0 #색약
visited = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if grid[i][j] == 'R':
            grid[i][j] = 'G'

for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            bfs(i, j)
            cw += 1
print(cw)