[백준/Python] (G5)10026 - 적록색약

 

적록색약 성공다국어

한국어   

 

10026번: 적록색약

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

53067

30524

23330

56.537%

문제

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

크기가 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

이 문제같은 경우엔 깊이우선탐색으로 풀 수 있다.

 

하지만 이 문제를 풀기 전엔 깊이우선탐색에 대하여 개념이 부족해 공부를 하고 나서 풀었다.

 

깊이 우선탐색으로 풀이를 진행하는데 일단, 케이스가 두가지라는점을 알아야한다.

1. RGB모두 구별할 경우

2. RG를 구별 못해서 (RG)B 두가지 경우로 나눠 풀 경우

 

일단 1번같은 경우에는 그냥 깊이우선탐색알고리즘으로 매개변수를 3개 받아서 풀었다.(x,y,색깔타입)

2번에서는 색깔타입을 구분해서 넣기 힘들기 때문에 숫자로 케이스를 구분해서 풀었다.

 

#11026 적록색약
from collections import deque
import sys
sys.setrecursionlimit(10**6)

n = int(input())
li = []
li2 = []
for _ in range(n):
    tmp = list(input())
    li.append(tmp.copy())
    li2.append(tmp.copy())

def dfs(x,y,t):
    if x <= -1 or x >= n or y <= -1 or y >= n:
        return False
    
    if li[x][y] == t and li[x][y] != 0:
        li[x][y] = 0
        dfs(x - 1,y,t)
        dfs(x + 1,y,t)
        dfs(x,y - 1,t)
        dfs(x,y + 1,t)
        return True
    return False

def dfs2(x,y,c):
    if x <= -1 or x >= n or y <= -1 or y >= n:
        return False
    
    if c == 1:
        if (li2[x][y] == 'R' or li2[x][y] == 'G') and li2[x][y] != 0:
            li2[x][y] = 0
            dfs2(x - 1,y,1)
            dfs2(x + 1,y,1)
            dfs2(x,y - 1,1)
            dfs2(x,y + 1,1)
            return True
        return False 
    if c == 2:
        if (li2[x][y] == 'B') and li2[x][y] != 0:
            li2[x][y] = 0
            dfs2(x - 1,y,2)
            dfs2(x + 1,y,2)
            dfs2(x,y - 1,2)
            dfs2(x,y + 1,2)
            return True
        return False 

#rgb
result = [0,0,0]
for i in range(n):
    for j in range(n):
        if dfs(i,j,'R') == True:
            result[0] += 1
        if dfs(i,j,'G') == True:
            result[1] += 1
        if dfs(i,j,'B') == True:
            result[2] += 1

print(sum(result),end = ' ')

result = [0,0]
for i in range(n):
    for j in range(n):
        if dfs2(i,j,1) == True:
            result[0] += 1
        if dfs2(i,j,2) == True:
            result[1] += 1
print(result[0] + result[1])

DFS 함수를 두개로 만들어서 케이스를 구분했다. 

 

애먹은 점은 한 배열에 대하여 색약이 아닌경우 계산을 했을 때 , 색약인경우로 넘어가면 리스트가 이전 계산 결과때문에 모두 0으로 초기화 된다는 점이였다.

처음에는 li에 깊은복사를 진행하여 arr에 넣는 식으로 풀었었지만, 생각해보니 리스트 안에 리스트는 그대로 참조연산이기 때문에 리스트 안에 있는 리스트를 깊은복사로 진행해야 한다는 점이였고,

 

또 하나는 DFS를 재귀함수로 구현했기 때문에 파이썬에서 정한 재귀함수 최대 깊이에 걸린다는 점이였다.

 

이는 sys라이브러리의 setrecursionlimit함수를 통해 최대 깊이를 늘려서 해결했다.