[알고리즘] 백준 파이썬 10026 적록색약

📍 문제 탐색하기

이번 문제인 적록색약 문제는 N×N 크기의 그리드에서 일반인과 적록색약이 각각 보는 색상의 구역 수를 계산하는 문제이다. 이 문제에는 다음과 같은 조건이 있다.

1. 같은 색상으로 이루어진 구역을 계산한다.
   • 상하좌우로 연결된 칸이 같은 색상이라면 같은 구역으로 간주한다.
2. 적록색약인 사람은 R(빨강)과 G(초록)을 같은 색상으로 인식한다.
   • 즉, R과 G는 동일한 색상으로 취급된다.
3. B(파랑)는 적록색약 여부와 상관없이 독립적으로 취급된다.

---

입력 범위

1 ≤ N ≤ 100
그리드의 각 칸은 R(빨강), G(초록), B(파랑) 중 하나로 색칠되어 있다.

---

가능한 시간복잡도

• 최대 N = 100 → 그리드 크기 = 100 × 100 = 10,000
• BFS를 사용해 모든 칸을 방문하며 구역을 계산 → 시간복잡도 O(N²).
• 두 개의 BFS(일반인, 적록색약 각각)를 수행하므로 O(2 × N²)로 충분히 처리 가능하다.
• 사실 처음엔 이걸 일반인, 적록색약 각각 돌리는 게 맞나 생각했는데, 시간 복잡도를 보니 그냥 각각 돌려도 될 것 같아서 각각 돌리기로 했다! (시간복잡도의 중요성)

---

📍 코드 설계하기

입력 처리

1. 입력으로 주어진 그림을 저장한다.
2. 적록색약인 사람이 보는 그림을 변환하여 별도로 저장한다.
   • R과 G를 동일하게 R로 변환!

구역 탐색

1. BFS로 상하좌우를 탐색하여 구역의 크기를 계산한다.
2. 탐색한 구역은 visited 배열로 관리하여 중복 방문을 방지한다.

결과 출력

1. 일반인의 구역 수를 계산
2. 적록색약의 구역 수를 계산
3. 두 값을 출력

---

📍코드 구현

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

N = int(input())
rgb = []

for _ in range(N):
    rgb.append(list(input().strip())) 

# 적록색약
rb = [['R' if color == 'G' else color for color in row] for row in rgb]

# 방향 벡터 (상, 하, 좌, 우)
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def bfs(r, c, visited, grid):
    queue = deque([(r, c)])
    visited[r][c] = True
    color = grid[r][c]
    
    while queue:
        r, c = queue.popleft()
        
        for k in range(4):
            nr = r + dx[k]
            nc = c + dy[k]
            
            if 0 <= nr < N and 0 <= nc < N and not visited[nr][nc] and grid[nr][nc] == color:
                visited[nr][nc] = True
                queue.append((nr, nc))

def count(grid):
    visited = [[False] * N for _ in range(N)]
    cnt = 0
    
    for i in range(N):
        for j in range(N):
            if not visited[i][j]:
                cnt += 1
                bfs(i, j, visited, grid)
                
    return cnt 

normal_cnt = count(rgb)
not_normal_cnt = count(rb)

print(normal_cnt, not_normal_cnt)