[BOJ] 10026. 적록색약

📌 문제 제목

문제 링크: BOJ 10026

---

🗒️ 문제 설명

R, G, B로만 칠해진 N x M 크기의 그림이 있다.

적록색약인 사람이 봤을 때 그림의 구역의 수와 적록색약이 아닌 사람이 봤을 때 구역의 수를 구하여라.

시간 제한: 1초

메모리 제한: 128MB

1 <= N <= 100

---

💡 문제 해결 아이디어

• 그래프를 적록색약인 사람과 적록색약이 아닌 사람 두 개로 만들어서 풀면 된다.
• 인풋이 R, G, B가 모두 있는 그림이므로 이중 for문을 돌면서 R와 G을 T로 둔 적록색약형 그림을 그린다.
• 적록색약형 그림과 적록색약이 아닌 형 그림을 BFS로 돌면서 구역의 개수를 구한다.
• BFS에 color를 매개변수로 넘겨서 상하좌우에 color가 같고 아직 방문하지 않았으면 큐에 추가

---

⌛️ 시간 복잡도

• O(N^2)

---

✅ 최종 코드

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

N = int(input().strip())
graph = [input().strip() for _ in range(N)]
b_graph = [['B'] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if graph[i][j] == 'R' or graph[i][j] == 'G':
            b_graph[i][j] = 'T'

direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]


def bfs(graph, x, y, visited, color):
    queue = deque([(x, y)])
    visited[x][y] = True
    while queue:
        xp, yp = queue.popleft()
        for dx, dy in direction:
            nx, ny = xp + dx, yp + dy
            if not (0 <= nx < N and 0 <= ny < N):
                continue
            if graph[nx][ny] == color and not visited[nx][ny]:
                queue.append((nx, ny))
                visited[nx][ny] = True


visited = [[False] * N for _ in range(N)]
b_visited = [[False] * N for _ in range(N)]

answer = 0
b_answer = 0

for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            bfs(graph, i, j, visited, graph[i][j])
            answer += 1

for i in range(N):
    for j in range(N):
        if not b_visited[i][j]:
            bfs(b_graph, i, j, b_visited, b_graph[i][j])
            b_answer += 1

print(answer, b_answer)