💻 백준 10026: 적록색약

문제 소개 🧐

N×N 그리드에 R, G, B 색상이 칠해져 있을 때
같은 색상으로 이루어진 ‘구역’의 개수를 세는 문제

  • 적록색약인 경우 R과 G를 같은 색으로 취급
  • 적록색약이 아닌 사람과 적록색약인 사람이 보는 구역의 수를 각각 계산해서 출력

입력 📝

  • 첫째 줄에 그리드의 크기 N이 주어져
  • 둘째 줄부터 N개의 줄에는 그림의 색상 정보가 주어져

출력 📤

  • 적록색약이 아닌 사람이 본 구역의 수와
  • 적록색약인 사람이 본 구역의 수를 공백으로 구분해 출력

제한 ❌

  • 시간: 1초
  • 메모리: 128 MB
  • N: 1 ≤ N ≤ 100

첫 번째 시도: BFS 탐색 🚀

Idea

이 문제는 그래프 탐색의 전형적인 예시라고 생각했다
그래서 너비 우선 탐색(BFS)을 사용해 풀기로 생각함

  1. 일반적인 경우:
    • 전체 그리드를 순회하면서 아직 방문하지 않은 칸을 찾고
    • 해당 칸에서부터 BFS를 시작해 같은 색으로 연결된 모든 칸을 방문 처리했다
    • 한 번의 BFS가 끝나면 하나의 구역을 찾은 것이므로, 구역 수를 1 증가시킨다
  2. 적록색약의 경우:
    • 입력받은 그림에서 모든 ‘R’을 ‘G’로 바꾸면
    • 적록색약이 보는 그림과 똑같아질 거라고 생각했다
    • 이 변환된 그림에 대해 위와 동일한 BFS를 한 번 더 수행하면 되겠다고 판단했다

Code

import sys
from collections import deque
import re

n = int(sys.stdin.readline().rstrip())
color_map = [sys.stdin.readline().rstrip() for _ in range(n)]  #  색깔 맵
d_pos = [(1,0), (-1,0), (0,-1), (0,1) ] # 하 상 좌 우

def get_area_cnt(color_map, n):
# 구역의 수
    cnt = 0
    que = deque()
    visited_node = [[False for _ in range(n)] for _ in range(n)]  # 방문한 노드 표시

    for i in range(n):
        for j in range(n):
            if visited_node[i][j]:
                continue
            else:
                visited_node[i][j] = True  # 이제 쓸거니깐 방문 표시  
        
            color = color_map[i][j]
            que.append((i,j))
        
            while que:
                x, y = que.pop()
                for d_x, d_y in d_pos:
                    next_x = x + d_x
                    next_y = y + d_y
                    # index 범위 안이고, 방문한적 없고, 색이 같다면 조건 통과
                    if 0 <= next_x < n and 0 <= next_y < n and not visited_node[next_x][next_y] and color_map[next_x][next_y] == color:
                        que.appendleft((next_x, next_y))
                        visited_node[next_x][next_y] = True
            cnt += 1 # 구역 하나 돌았으니깐 구역수 +1
    return cnt

ans1 = get_area_cnt(color_map, n)

# 적색 -> 녹색 변환
color_map_II = []
for color in color_map:
    color_map_II.append(re.sub('R','G', color))

ans2 = get_area_cnt(color_map_II, n)

print(ans1, ans2)

Result

  • 성공! 🎉
  • 두 가지 경우를 나누어 생각하고, BFS를 두 번 적용하는 아이디어가 잘 통한 것 같다

개선할 부분 🤔

  • 적록색약 그림을 만들 때 re.sub()를 사용했는데
  • 단순한 문자열 치환이라 str.replace()가 더 간단하고 빨랐을 것 같다
  • 다음에는 상황에 맞는 적절한 함수를 선택하도록 더 신경 써야겠다