[TIL] 백준 10026 - 적록색약 ( python )

📌 문제 탐색하기

N : 그리드 행, 열

R : 빨강

G : 초록

B : 파랑

 

적록색약 : 빨간색과 초록색의 차이 못느낌
적록색약이 아닌 사람이 봤을 때의 구역의 수와 적록색약인 사람이 봤을 때의 구역의 수를 구하는 것이 핵심입니다.

• 1≤N≤100

가능한 시간복잡도

N의 최댓값은 100이므로 전체 나무판의 수는 100 * 100 = 10,000개입니다.

외부 이중 반복문과 BFS 모두 O(N^2) 시간복잡도를 가지므로, 최악의 경우에도 약 10,000번의 기본 연산을 수행합니다.

1초에 약 100,000,000번의 연산을 수행할 수 있으므로 시간 안에 탐색을 완료할 수 있습니다.

알고리즘 선택

 BFS 알고리즘으로 접근해 보겠습니다.

---

📌 코드 설계하기

1. 문제의 Input을 받습니다.
2. matrix의 원본 데이터를 복사하여 blindness_matrix를 생성합니다.
3. blindness_matrix의 'G'구역을 'R'구역으로 변경합니다.
4. 방문 체크를 위한 visited와 blindness_visted 배열을 초기화합니다.(False)
5. BFS 탐색을 구현합니다.
   1. 초기 시작 노드를 방문 체크한 후 queue에 탐색할 좌표와 색상(color)을 넣습니다.
   2. dy, dx를 활용해 상하좌우 이동하면서 같은 색상(color)을 가진 위치를 탐색합니다.
   3. 방문한 위치는 visited로 체크하여 중복 방문 방지합니다.
6. 각 BFS 실행마다 새로운 구역을 하나로 인식하여 개수를 count, blindness_count에 저장합니다.
7. count와 blindness_count를 출력합니다. 

---

📌 정답 코드

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

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

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

    while q:
        y, x, color = q.popleft()

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]

            if 0 <= ny < N and 0 <= nx < N and not visited[ny][nx] and matrix[ny][nx] == color:
                visited[ny][nx] = True
                q.append((ny, nx, matrix[ny][nx]))

N = int(input())
matrix = [list(input().strip()) for _ in range(N)]
blindness_matrix = [list(row) for row in matrix]

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

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

count = 0
blindness_count = 0

for y in range(N):
    for x in range(N):
        if not visited[y][x]:
            bfs(y, x, matrix, visited)
            count += 1
        if not blindness_visited[y][x]:
            bfs(y, x, blindness_matrix, blindness_visited)
            blindness_count += 1

print(count, blindness_count)