백준 10026번 - 적록색약

적록색약 문제 바로 가기

풀이 날짜: 2026-01-05

baekjoon 알고리즘 문제 풀이

풀이 코드


import sys
input = sys.stdin.readline
from collections import deque

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

n = int(input())
graph = [list(input().strip()) for _ in range(n)]

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

    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y

            if 0<=nx<n and 0<=ny<n and not visited[ny][nx]:
                current = graph[ny][nx]

                if not blind:
                    if current == start:
                        visited[ny][nx] = True
                        q.append((nx,ny))

                else:
                    if start in ('R', 'G'):
                        if current in ('R', 'G'):
                            visited[ny][nx] = True
                            q.append((nx,ny))
                    else:
                        if current == 'B':
                            visited[ny][nx] = True
                            q.append((nx,ny))

visited1 = [[False]*n for _ in range(n)]
normal = 0
for y in range(n):
    for x in range(n):
        if not visited1[y][x]:
            bfs(x,y,visited1,blind=False)
            normal +=1

visited2 = [[False]*n for _ in range(n)]
blind = 0
for y in range(n):
    for x in range(n):
        if not visited2[y][x]:
            bfs(x,y,visited2,blind=True)
            blind+=1

print(normal, blind)
  

문제 핵심 요약:

같은 색이 상/하/좌/우로 연결된 덩어리(구역)가 몇 개인지 세는 문제이다.
즉, 연결된 영역을 통째로 묶는 연결요소 탐색인 문제였다.
따라서 구역을 확장하면서 같은 구역을 전부 표시하는 것이 목표이다.


전체 구조: 전체 순회 + 방문 안 한 칸에서 BFS 시작

그래프 전체를 (x,y)로 순회하다가 visited[y][x] == False인 칸을 발견하면, 그 칸은 아직 어떤 구역에도 포함되지 않은 ‘새 구역의 시작점’이다.
따라서 그 순간 bfs()를 호출하고, BFS가 끝나면 그 구역이 전부 방문 처리되기 때문에 구역의 개수(count)를 1 증가시킨다.
즉 이 문제에서 BFS를 몇 번 호출했는지 세는 것이다.


BFS 함수 인자를 어떻게 결정했는가

bfs(x,y,visited,blind)처럼 인자를 설정한 이유는 “bfs를 실행할 때마다 달라지는 정보”를 함수에 넣기 위해서였다.
시작 좌표(x,y)는 매번 달라지고, visited도 일반 시야/적록색약 시야에 따라 서로 다른 배열을 써야 하므로 인자로 넘겨야 했다.
또한 blind는 색 비교 규칙을 바꾸는 옵션(모드)으로 처리하여, 같은 bfs 구조를 유지하면서도 비교 조건을 바꾸는 데 적용했다.


blind 처리: “색 비교 규칙만 바꾸기”

이 코드에서 blind는 BFS의 구조를 바꾸는 게 아니라, 색 비교 규칙만 바꾸는 스위치이다.
blind=False이면 current == start일 때만 같은 구역으로 인정한다.
하지만 blind = True이면 “R과 G를 같은 색으로 취급”해야 하기 때문에, 시작 색이 R 또는 G일 때는 이웃 색이 R 또는 G이면 같은 구역으로 인정했다.
반대로 시작 색이 B라면 이웃 지역도 B일 때만 같은 구역으로 한다.


왜 visited를 두 개를 썼는가

정상 시야와 적록색약 시야는 구역을 세는 기준이 다르기 때문에 방문 상태를 공유하면 안 된다.
따라서 visited1으로 일반 시야 구역을 세고, visited2로 적록색약 구역을 따로 센다. 같은 graph를 두 번 탐색하지만, 방문 배열이 다르기 때문에 결과가 다르게 나온다.