[백준] 10026. 적록색약

nayoon·2021년 2월 8일
0

Algorithm

목록 보기
4/55

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

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

다음과 같은 그림이 있다.

일반인이라면 아래와 같이 구분되어 보여야한다.

하지만 적록색약인 경우 아래와 같이 보인다고 한다.

같은 색깔을 가진 section으로 구분짓는 문제이고 나는 파이썬을 이용해서 DFS로 풀었다.

# 적록색약
# dfs
import sys
sys.setrecursionlimit(100000) # 설정해주지 않으면 RecursionError 런타임 에러가 날 거다.
# 백준 채점 서버에서는 파이썬 재귀 한계값이 1000
# 위의 설정을 통해서 재귀 limit을 100000으로 바꿔주었다.

n = int(input())
rg = [list(input()) for _ in range(n)]
visited = [[False]*n for _ in range(n)]

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

def dfs(x, y):
    visited[x][y] = True
    
    color = rg[x][y]

    for i in range(4):
        nx = dx[i] + x
        ny = dy[i] + y
        if -1 < nx < n and -1 < ny < n :
            if rg[nx][ny] == color and visited[nx][ny]==False: # 색깔이 같고 방문한 적이 없으면 section에 포함
                dfs(nx, ny)
# 적록색약 X
answer = 0
for i in range(n):
    for j in range(n):
        if visited[i][j] == False: # 이미 방문했으면 dfs 돌릴 필요 X / 이미 계산된 section
            dfs(i, j)
            answer+=1

# 적록색약 

# R -> G 으로 바꾸기
color_weak_answer = 0
for i in range(n):
    for j in range(n):
        if rg[i][j] == 'R':
            rg[i][j] = 'G'
          
# 방문배열 초기화
visited = [[False]*n for _ in range(n)]

# 적록색약 dfs
for i in range(n):
    for j in range(n):
        if visited[i][j] == False:
            dfs(i, j)
            color_weak_answer += 1

print(answer, color_weak_answer)

RecursionError가 발생했고 위와 같이 sys.setrecursionlimit()을 설정해서 해결하였다.

import sys를 해주지 않아 NameError도 경험하였다.

profile
뚜벅뚜벅 열심히 공부하는 개발자

0개의 댓글