[백준 10026] 적록색약(Python)

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

문제이해

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

문제 포인트

기본적인 탐색으로 한번 탐색을 완료한 뒤에 적록색약을 고려하여 하나의 색상으로 통일 그 이후에 탐색후 정답을 제출하면 된다

제출 코드

import sys
from collections import deque

N = int(sys.stdin.readline().strip())
graph = [list(map(str, sys.stdin.readline().strip())) for _ in range(N)]
q = deque()
dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]


def bfs(y, x):
    visited[y][x] = True
    q.append((y, x))

    while q:
        cur_y, cur_x = q.popleft()

        for i in range(4):
            next_y = cur_y + dy[i]
            next_x = cur_x + dx[i]

            if 0 <= next_y < N and 0 <= next_x < N:
                if graph[cur_y][cur_x] == graph[next_y][next_x]:
                    if not visited[next_y][next_x]:
                        visited[next_y][next_x] = True
                        q.append((next_y, next_x))
# 색약이 아닌 사람
visited = [[False] * N for _ in range(N)]
cnt1 = 0
for y in range(N):
    for x in range(N):
        if not visited[y][x]:
            bfs(y, x)
            cnt1 += 1

for y in range(N):
    for x in range(N):
        if graph[y][x] == 'G':
            graph[y][x] = 'R'

visited = [[False] * N for _ in range(N)]
cnt2 = 0
for y in range(N):
    for x in range(N):
        if not visited[y][x]:
            bfs(y, x)
            cnt2 += 1

print(cnt1, cnt2)