[BFS] 백준 #10026 적록색약 - Python

🗂️ 문제

링크: https://www.acmicpc.net/problem/10026

 

💡 접근법

적록색약인 경우 R과 G를 같은 색으로 취급한다.

따라서 BFS를 일반 BFS와 적록색약을 처리하는 BFS 두 함수를 정의하고, 적록색약을 처리하는 BFS 함수에서(color == "R" or color == "G") and (maps[nx][ny] == "R" or maps[nx][ny] == "G") 조건을 통해 R과 G를 같은 색으로 처리한다.

 

아니면, 적록색약용 맵(R을 모두 G로 변경)을 따로 생성하여 정상인을 처리할 때와 동일한 BFS를 사용할 수도 있다.

 

😎 내 코드

(1) 적록색약 유무에 따른 BFS 함수 분리

import sys
from collections import deque

N = int(sys.stdin.readline())
maps = []
for _ in range(N):
    line = sys.stdin.readline().strip()
    maps.append([l for l in line])


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


def BFS_normal(x, y, color):
    queue = deque([(x, y)])
    while queue:
        x, y = queue.popleft()
        for ax, ay in zip(dx, dy):
            nx = x + ax
            ny = y + ay
            if N > nx >= 0 and N > ny >= 0:
                if not visited[nx][ny] and color == maps[nx][ny]:
                    visited[nx][ny] = True
                    queue.append((nx, ny))


def BFS_abnormal(x, y, color):
    queue = deque([(x, y)])
    while queue:
        x, y = queue.popleft()
        for ax, ay in zip(dx, dy):
            nx = x + ax
            ny = y + ay
            if N > nx >= 0 and N > ny >= 0:
                if not visited[nx][ny]:
                    if (color == "R" or color == "G") and (maps[nx][ny] == "R" or maps[nx][ny] == "G"):
                        visited[nx][ny] = True
                        queue.append((nx, ny))
                    elif color == "B" and maps[nx][ny] == "B":
                        visited[nx][ny] = True
                        queue.append((nx, ny))


normal_cnt = 0
visited = [[False] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            normal_cnt += 1
            BFS_normal(i, j, maps[i][j])

abnormal_cnt = 0
visited = [[False] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            abnormal_cnt += 1
            BFS_abnormal(i, j, maps[i][j])

print(normal_cnt, abnormal_cnt)

 

(2) 적록색약용 새로운 맵 생성

import sys
import copy
from collections import deque

N = int(sys.stdin.readline())
maps = []
for _ in range(N):
    line = sys.stdin.readline().strip()
    maps.append([l for l in line])


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


def BFS(x, y, color, grid):
    queue = deque([(x, y)])
    while queue:
        x, y = queue.popleft()
        for ax, ay in zip(dx, dy):
            nx = x + ax
            ny = y + ay
            if N > nx >= 0 and N > ny >= 0:
                if not visited[nx][ny] and color == grid[nx][ny]:
                    visited[nx][ny] = True
                    queue.append((nx, ny))


normal_cnt = 0
visited = [[False] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            normal_cnt += 1
            BFS(i, j, maps[i][j], maps)

abnormal_maps = copy.deepcopy(maps)  # 원본 유지하며 새 맵 생성
for i in range(N):
    for j in range(N):
        if abnormal_maps[i][j] == "R":
            abnormal_maps[i][j] = "G"

abnormal_cnt = 0
visited = [[False] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            abnormal_cnt += 1
            BFS(i, j, abnormal_maps[i][j], abnormal_maps)

print(normal_cnt, abnormal_cnt)

 

✅ 정답 확인