[BOJ] 1780 : 종이의 개수 [분할](Python)

문제 링크

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

1780번: 종이의 개수

소스 코드

import sys
input = sys.stdin.readline

n = int(input().rstrip())

graph = []
for i in range(n):
    graph.append(list(map(int,input().rstrip().split())))

answer = {-1:0, 0:0, 1:0} # 카운트를 저장할 딕셔너리

def dfs(x,y,n):
    if n == 1: # 길이 1짜리 사각형이면 그대로 카운트
        answer[graph[x][y]] += 1
        return
    
    stand = graph[x][y] # 사각형의 맨 왼쪽 위 숫자가 기준
    for i in range(x,x+n): # 사각형 탐색
        for j in range(y,y+n):
            # 기준과 다른 숫자가 발견되면
            if graph[i][j] != stand:
                n //= 3 # 사각형을 9로 쪼개기
                dfs(x,y,n) # 1행
                dfs(x,y+n,n)
                dfs(x,y+2*n,n)
                
                dfs(x+n,y,n) # 2행
                dfs(x+n,y+n,n)
                dfs(x+n,y+2*n,n)
                
                dfs(x+2*n,y,n) # 3행
                dfs(x+2*n,y+n,n)
                dfs(x+2*n,y+2*n,n)
                return # 쪼갰으면 기존의 탐색은 종료

    # 사각형 전부 기준과 같은 숫자인 경우 카운트
    answer[stand] += 1
    return

dfs(0,0,n) # (0,0)에서 시작

for i in range(-1,2): # 딕셔너리 value 뽑아오기
    print(answer[i])

 

해설

• 분할, 재귀, DFS
• 탐색 중 다른 숫자가 나오면 n을 3으로 나눠 다시 탐색

DFS를 이용한 재귀를 통해 분할을 시도할 수 있다.

중요한 것은 n을 반복해서 3으로 나눠주는 것, n이 1이 되었을 때는 그대로 return 하는 것, 9개로 쪼갤 수 있도록 범위를 잘 설정하는 것이다.

 

n == 1인 경우 graph[x][y] 를 key로 삼아 카운트

n이 1이 되면 종이를 더이상 작게 자를 수 없다.

따라서 해당 좌표의 값을 바로 딕셔너리의 키로 삼아서 카운트 해야 한다.

 

예를 들어 graph[0][0] = 0인 경우, answer[0] += 1 이 되는 것이다.

 

그래프 탐색 중 기준과 다른 숫자가 나오면 n을 3으로 나누기

n을 3으로 나누는 것은 범위 때문이다.

애초에 문제에서 n은 3^k 꼴이라고 명시되어 있다.

따라서 n을 3으로 나누면 지금 탐색하는 종이의 1/3 범위를 보겠다는 뜻이므로 이를 가로와 세로에 모두 적용하면 9분할이 된다.

 

이때 신경써야 하는 것은 for문의 범위와, 재귀 함수에 부여하는 매개변수다.

for문을 보면 x부터 x+n까지, y부터 y+n까지로 되어 있다.

즉, 변경된 사각형의 size를 반영하여 탐색을 수행할 수 있도록 for문의 범위와 매개변수를 잘 설정해야 한다.

위 소스코드에서는 순서대로 1행, 2행, 3행을 재귀 함수를 통해 탐색하도록 설정했다.

 

애초에 기준과 다른 숫자가 존재해서 9분할을 시도하는 순간, 이 탐색은 잘못된 케이스라는 뜻이다.

이 종이에는 다른 숫자가 섞여 있다는 것이기 때문에 9분할 이후 바로 return 하여 추가 탐색을 막아준다.

 

 

그래프 탐색 중 기준과 다른 숫자가 없던 경우

이때는 사각형 내의 모든 숫자가 기준과 같다는 뜻이다.

즉, 문제에서 요구하는 같은 숫자로만 채워진 종이에 해당하는 경우다.

따라서 이때의 기준을 곧 딕셔너리의 키로 삼는다.

 

위의 예와 마찬가지로 x,y = 0,0 이고, graph[x][y] = 0 = stand 인 경우, answer[0] += 1 이 되는 것이다.

 

 

마지막으로는 answer에 누적된 종이의 수를 하나씩 꺼내어 출력하면 된다.