[BOJ] #10026 적록색약 (Python)

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

🚀

알고리즘 분류 🔗

그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

🚀

문제 설명 🔗

적록색약은 빨간색과 초록색을 구별하지 못하는 사람을 말한다.

N x N 크기의 그림이 주어지고, 각 칸에는 R, G, B 중 하나의 색이 칠해져 있습니다.

적록색약은 R과 G를 구별하지 못하므로, R과 G는 같은 색으로 간주합니다.

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

위의 그림에서 적록색약이 아닌 사람은 4개의 영역으로 나누어 볼 수 있습니다.

적록색약인 사람은 3개의 영역으로 나누어 볼 수 있습니다.

적록색약이 아닌 사람이 그림을 보고 구분할 수 있는 영역의 개수와 적록색약인 사람이 구분할 수 있는 영역의 개수를 출력하세요.

✅

입력 🔗

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개의 줄에 걸쳐 그림이 주어진다.

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

✅

출력 🔗

공백을 구분으로 두 줄에 걸쳐 적록색약이 아닌 사람이 구분할 수 있는 영역의 개수와 적록색약인 사람이 구분할 수 있는 영역의 개수를 출력한다.

4 3

🚀

풀이 🔗

BFS(너비 우선 탐색) 알고리즘을 사용하여 각 구역을 탐색합니다.
적록색약인 경우 R과 G를 같은 색으로 간주하여 탐색합니다.
BFS를 사용하여 각 구역을 탐색하고, 방문한 칸은 visited 배열로 체크합니다.
BFS는 큐를 사용하여 구현하며, 상하좌우로 연결된 같은 색의 칸을 탐색합니다.
각 구역을 탐색할 때마다 카운트를 증가시킵니다.
최종적으로 적록색약이 아닌 사람과 적록색약인 사람이 구분할 수 있는 영역의 개수를 출력합니다.

🚀

코드 - Python 🔗

import sys
from collections import deque
 
sys.setrecursionlimit(10000)  # 재귀 제한 해제 (DFS 쓸 경우 대비)
N = int(sys.stdin.readline())
 
 # 색상 격자 입력 받기
grid = [list(sys.stdin.readline().strip()) for _ in range(N)]
 
 # 상하좌우 방향 정의
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
 
 # BFS로 한 구역 탐색하는 함수
def bfs(x, y, visited, board, is_amblyopia):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True  # 현재 위치 방문 처리
    current_color = board[x][y]
 
    while queue:
        cx, cy = queue.popleft()
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
 
            # 범위를 벗어나거나 이미 방문한 경우 무시
            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
                next_color = board[nx][ny]
 
                if is_amblyopia:
                    # 적록색약인 경우: R과 G는 같은 색으로 간주
                    if (current_color in "RG" and next_color in "RG") or current_color == next_color:
                        visited[nx][ny] = True
                        queue.append((nx, ny))
                else:
                    # 일반인: 정확히 같은 색만 같은 구역
                    if next_color == current_color:
                        visited[nx][ny] = True
                        queue.append((nx, ny))
 
 # 전체 격자를 순회하면서 BFS 시작 지점을 찾아 구역 수 세기
def count_areas(is_amblyopia):
    visited = [[False]*N for _ in range(N)]
    count = 0
    for i in range(N):
        for j in range(N):
            if not visited[i][j]:
                bfs(i, j, visited, grid, is_amblyopia)
                count += 1  # BFS 한 번 돌면 하나의 구역
    return count
 
 # 결과 계산 및 출력
normal = count_areas(False)       # 일반인의 시각
color_blind = count_areas(True)   # 적록색약인의 시각
print(normal, color_blind)

🚀

핵심 🔗

✅

BFS 탐색 🔗

BFS를 사용하여 한 구역을 탐색하고, 방문한 칸은 visited 배열로 체크합니다.
BFS는 큐를 사용하여 구현하며, 상하좌우로 연결된 같은 색의 칸을 탐색합니다.

✅

시간 복잡도 🔗

O(N^2)

: 각 칸을 최대 한 번만 방문

N ≤ 100 이므로 충분히 효율적

추천 포스트

[BOJ] #10026 적록색약 (Python)Color Weakness (Python)