[BOJ] 10026번 | 적록색약 (Python3)

🔗문제 보러가기

10026번: 적록색약

 

 

문제 설명

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

 

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1) 그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

 

---

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
둘째 줄부터 N개 줄에는 그림이 주어진다.

 

---

출력

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

---

예제 입출력

 

---

풀이 전략

DFS/BFS에 취약하다는 걸 깨닫고, 우선 DFS 문제부터 풀어 봐야지 하고 백준 온라인 저지에 들어가 봤다.

그리고 마주하게 된 문제가 바로 다음 문제였다. 나중에 확인한 사실인데, 난이도 골드 5짜리 문제였다. 처음 도전하는 나에게는 벅찬 수준이 아니었을까?.... 풀었던 전략을 소개하자면 다음과 같다.

1. 시작 위치의 색깔 정보를 가지고, 주변에 같은 색깔을 가진 게 없는지 상, 하, 좌, 우 방향으로 최대 깊이까지 들어간다.
   •  방문한 곳은 별도의 문자로 표시한다.
2. 인덱스를 벗어나거나, 더 이상 같은 색깔을 가진 게 없으면 탐색을 종료한다.
3. 2차원 리스트를 순회하며, 방문했던 곳은 생략한 채로 DFS를 계속 진행한다.

 

---

소스 코드 및 결과

import sys
sys.setrecursionlimit(10**6) # 재귀함수 호출 한계치를 늘리기 위해 필수

n = int(input())
graph = []

# 색깔 정보 받기
for _ in range(n):
  graph.append(list(input()))


def DFS(graph, color, x, y, hasBlind):
  if x < 0 or x >= n or y < 0 or y >= n:  # 유효한 인덱스가 아니라면 종료
      return False
  
  if hasBlind:   # 적록색약을 가진 사람일 경우
      if (graph[x][y] == 'R' or graph[x][y] == 'G') and (color == 'R' or color == 'G'):
          color = graph[x][y] 
  
  if graph[x][y] == color:     # 같은 색깔일 경우
      graph[x][y] = '#'        # 방문 처리
      DFS(graph, color, x - 1, y, hasBlind)  # 상
      DFS(graph, color, x + 1, y, hasBlind)  # 하
      DFS(graph, color, x, y - 1, hasBlind)  # 좌
      DFS(graph, color, x, y + 1, hasBlind)  # 우
      # 주변을 다시 탐색
     
      return True  # 모든 DFS를 마쳤을 경우
  return False     # 주변에 같은 색깔인 게 없을 경우


generalResult = 0
blindnessResult = 0
generalGraph = [_list.copy() for _list in graph]
blindGraph = [_list.copy() for _list in graph]


for i in range(n):
  for j in range(n):
    if generalGraph[i][j] != '#':
        if DFS(generalGraph, generalGraph[i][j], i, j, False): # 일반 사람일 경우
          generalResult += 1
    
    if blindGraph[i][j] != '#':
        if DFS(blindGraph, blindGraph[i][j], i, j, True):      # 적록색약이 있는 사람일 경우
            blindnessResult += 1
    
print(generalResult, blindnessResult, end = ' ')

 

<이것이 코딩 테스트다. with 파이썬> 책의 예제를 보며 공부했던 DFS 코드를 사용하여 덧붙였다.

Visual Studio Code의 디버깅 기능을 통해 코드가 어떻게 진행되는지를 보면서 확인해봤다.

 

그리고 DFS 구현을 위해, 재귀 함수를 사용했는데 런타임 에러가 자꾸 떴었다.

알고보니, 파이썬의 기본 재귀 깊이 제한이 1000정도라 얕아서 발생한 문제였다.

그래서 파이썬으로 코딩 테스트를 볼 거면, 다음 코드를 통해 재귀 함수 호출 한계치를 늘려주고 시작하는 것이 좋다고 한다. 

import sys
sys.setrecursionlimit(10 ** 6)  # 1000000번으로 호출 한계치 설정