[백준/파이썬] 10026번: 적록색약

문제

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

풀이

• N×N 그리드의 각 칸에 R, G, B 중 하나를 색칠한 그림
• 그림은 구역으로 나누어져 있는데, 각 구역은 같은 색으로 이루어짐
• 상하좌우로 같은 색이 인접한 경우 같은 구역
• 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때의 구역 수 출력

예시를 통해 문제를 이해해 보겠습니다.
N = 5일 때 다음과 같이 그림이 이루어져 있습니다.

위 그림을 색약이 아닌 사람이 봤을 때 몇 개의 그룹으로 나뉘는지 보면 🧐

그림과 같이 4개의 그룹으로 이루어져 있습니다.

하지만, "적록색약"인 사람이 볼 경우엔 "빨간색"과 "초록색"을 구분하지 못하므로 3개의 그룹으로 이루어져 있습니다.

색약이 아닌 사람의 시점에서는 서로 다른 색일 경우에 다른 그룹으로 치기 때문에 이를 이용해 로직을 작성해 보겠습니다.

그래프 탐색을 이용하여 코드를 작성할 수 있는데, 저는 BFS 방식을 사용했습니다.

상하좌우 탐색을 위해 dx와 dy를 선언해주고 시작했습니다.

def bfs(graph, visited, a, b): # 탐색할 그래프, 방문 여부, 좌표 (a,b)
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

검사할 좌표 a,b를 deque()에 넣어주고 해당 좌표를 방문 처리했습니다.

    queue = deque([(a,b)])
    visited[a][b] = True

queue가 없을 때까지 반복
dx와 dy를 이용해 4방향 탐색을 진행해줬습니다.

    while queue:
        x,y = queue.popleft() # 탐색을 진행할 좌표
        
        for i in range(4): # 상하좌우 탐색
            nx = x + dx[i]
            ny = y + dy[i]
            # nx, ny가 범위 내에 존재 && 탐색하지 않은 좌표 && 탐색하려는 좌표가 기존 좌표의 색과 같을 경우
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and graph[x][y] == graph[nx][ny]:
                queue.append((nx,ny)) # queue에 추가
                visited[nx][ny] = True # 방문 처리
    
    return 1 # 1개의 그룹으로 리턴

1개의 그룹을 리턴해주는 함수를 만들었습니다.
이제 이걸 모든 좌표에 넣어서 방문하지 않은 경우에 탐색을 진행하는 함수를 만들어 보겠습니다.

def counting(graph): # 탐색을 진행할 그림
    visited = [[False] * n for _ in range(n)] # 방문 여부
    cnt = 0 # 리턴할 값

방문 여부를 선언했으니, 현재의 그림에서 방문하지 않은 좌표일 경우 탐색을 시작합니다.

	# N*N 만큼 반복
    for i in range(n):
        for j in range(n):
            if not visited[i][j]: # 방문하지 않은 좌표일 경우
                cnt += bfs(graph, visited, i, j) # 탐색 시작
    
    return cnt

탐색을 마치면 bfs를 몇 번 실행했는지 알 수 있습니다.

이렇게만 하면 색약이 아닌 사람의 그룹 수만 구할 수 있습니다.
이제 적록색약인 사람의 시점에서의 그룹 수를 구해야 합니다.

여기서 어떻게 진행해야 할까 오랜 시간 생각을 해봤는데, '적록색약인 사람들은 초록색과 빨간색을 구분 못하니 아예 같은 색으로 치환해버리면 어떨까?'란 생각이 갑자기 들었습니다 🤩

그래서, 우선 색약이 아닌 사람의 기준으로 그림을 입력 받아준 후,

    RGB = [list(input().rstrip()) for _ in range(n)]

이 그림을 G가 존재할 경우 이를 R로 치환해주었습니다 😁

    RB = [['R' if r == 'G' else r for r in row] for row in RGB] # 'G'일 경우 'R'로 치환 아닐 경우 원래 글자 삽입

이후에 이 그림들을 각각 counting 함수에 넣어주어 문제를 해결 🥳

코드

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

def bfs(graph, visited, a, b):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    queue = deque([(a,b)])
    visited[a][b] = True
    
    while queue:
        x,y = queue.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and graph[x][y] == graph[nx][ny]:
                queue.append((nx,ny))
                visited[nx][ny] = True
    
    return 1

def counting(graph):
    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 += bfs(graph, visited, i, j)
    
    return cnt

if __name__ == "__main__":
    n = int(input())
    RGB = [list(input().rstrip()) for _ in range(n)]
    RB = [['R' if r == 'G' else r for r in row] for row in RGB]        
    
    print(counting(RGB), counting(RB))