[boj.kr] 10026. 적록색약

Category	ps/bfs & dfs
Tag	bfs & dfs
Tags	queuerecursion
난이도	골드 5
메모	python recursion limit 기억하자
발행 여부
사이트	boj
이해	완벽히 이해
최종 편집 일시	@2021년 12월 19일 오후 11:45
푼 날짜	@2021년 12월 19일 오후 10:58

문제 해설 및 주의사항

원문

문제

입력

출력

예제 입력 1

예제 출력 1

주의사항

풀이

내 풀이 코드

풀이 코드 (다른 사람)

퇴고

문제 해설 및 주의사항

원문

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

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

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

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

출력

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

예제 입력 1

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

예제 출력 1

4 3

주의사항

• 적록색약은 R=G 라고 생각하겠군.

---

풀이

• 정상인 사람 과 적록색약인 사람 두 개로 나누어 연결 요소의 개수를 bfs 로 구해보자.

내 풀이 코드

import sys, collections, pprint
n = int(sys.stdin.readline())

board = [sys.stdin.readline().strip() for _ in range(n)]
m = len(board[0])

is_visited = [[0 for _ in range(m)] for _ in range(n)]

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

def dfs(y: int, x: int):
  # 방문 표시
  is_visited[y][x] = 1

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

    # 범위 체크
    if ny < 0 or ny >= n or nx < 0 or nx >= m:
      continue
    
    # 다음 칸의 색이 현재 칸의 색과 같다면
    if is_visited[ny][nx] == 0 and board[ny][nx] == board[y][x]:
      dfs(ny, nx)
  return None

def bfs(start_y: int, start_x: int):
  # 초기 설정
  Q = collections.deque()
  Q.append((start_y, start_x))
  is_visited[start_y][start_x] = 1

  # bfs 시작
  while Q:
    y, x = Q.popleft()
    
    for i in range(4):
      ny, nx = y + dy[i], x + dx[i]
      
      if ny >= 0 and ny < n and nx >= 0 and nx < m:
        if is_visited[ny][nx] == 0 and board[y][x] == board[ny][nx]:
          Q.append((ny, nx))
          is_visited[ny][nx] = 1
      

count_normal = 0
count_disabled = 0
for y in range(n):
  for x in range(m):
    if is_visited[y][x] == 0:
      bfs(y, x)
      count_normal += 1

# 방문 초기화
is_visited = [[0 for _ in range(m)] for _ in range(n)]
# board 색약화 
for idx, _ in enumerate(board):
  board[idx] = board[idx].replace("R", "G")
for y in range(n):
  for x in range(m):
    if is_visited[y][x] == 0:
      bfs(y, x)
      count_disabled += 1


print(count_normal, count_disabled)

• 처음 접근하였을 때, dfs 재귀로 구현하였으나, 그러다보니 recursionlimit 에 걸리게 되었다.
  • python 은 기본적으로 재귀의 깊이가 1000을 넘기면 오류를 발생시킨다.
  • 이를 근본적으로 해결하려면 sys.setrecursionlimit 으로 강제적으로 재귀 최대 깊이를 설정해주어야 한다.

• 이후, stack 을 활용한 dfs 로 구현하거나 queue 를 활용한 bfs 로 구현해보기로 하였다.
  • bfs 로 구현한 코드가 위의 bfs() 함수이다.

풀이 코드 (다른 사람)

import sys

sys.setrecursionlimit(1000000)
a = int(sys.stdin.readline())
graphForNomal= [([0] * a) for _ in range(a)]
graphForRedGreen= [([0] * a) for _ in range(a)]
count_Nomal = 0
count_Red_Green = 0

for i in range(a) :
    str = sys.stdin.readline()
    for j in range(a) :
        graphForNomal[i][j] = str[j]
        if str[j] == "R" :
            graphForRedGreen[i][j] = "G"
        else :
            graphForRedGreen[i][j] = str[j]

def nomal_Dfs(graph, color, sero, garo) :
    if garo + 1 < a and (color == graph[sero][garo + 1]):
        graph[sero][garo + 1] = "A"
        nomal_Dfs(graph, color, sero, garo + 1)

    if sero + 1 < a and (color == graph[sero + 1][garo]) :
        graph[sero + 1][garo] = "A"
        nomal_Dfs(graph, color, sero + 1, garo)

    if garo - 1 > -1 and (color == graph[sero][garo - 1]) :
        graph[sero][garo - 1] = "A"
        nomal_Dfs(graph, color, sero, garo - 1)

    if sero - 1 > -1 and (color == graph[sero - 1][garo]) :
        graph[sero - 1][garo] = "A"
        nomal_Dfs(graph, color, sero - 1, garo)

#이거 필요 없을듯..?
'''
def red_Green_Dfs(color, sero, garo) :
    if garo + 1 < a and ()
'''

for i in range(a) :
    for j in range(a) :
        if graphForNomal[i][j] != "A" :
            temp = graphForNomal[i][j]
            graphForNomal[i][j] = "A"
            count_Nomal = count_Nomal + 1
            nomal_Dfs(graphForNomal, temp, i, j)

for i in range(a) :
    for j in range(a) :
        if graphForRedGreen[i][j] != "A" :
            temp = graphForRedGreen[i][j]
            graphForRedGreen[i][j] = "A"
            count_Red_Green = count_Red_Green + 1
            nomal_Dfs(graphForRedGreen, temp, i, j)

print(count_Nomal, end = ' ')
print(count_Red_Green)

• 입력을 받음과 동시에 적록색약을 위한 그래프를 생성했다.

for i in range(a) :
    str = sys.stdin.readline()
    for j in range(a) :
        graphForNomal[i][j] = str[j]
        if str[j] == "R" :
            graphForRedGreen[i][j] = "G"
        else :
            graphForRedGreen[i][j] = str[j]

• 시간을 줄일 수 있는 비결인 듯 하다.

---

퇴고

• 재귀 깊이를 매우 깊게 하여 제출하였더니 메모리 초과가 발생하였다.

• 파이썬의 재귀 깊이 제한을 잘 기억하자.