[Python] S2_1780_종이의 개수💠

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

문제

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.

만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
(1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.
이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

출력

첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

예제

조건

• 시간 제한: 2초
• 메모리 제한: 256MB

코드

import sys
input = sys.stdin.readline

def DAC(x,y,n):
    global minusPaper, zeroPaper, onePaper
    first = papers[x][y]
    
    for i in range(x,x+n):
        for j in range(y,y+n):
            if papers[i][j] != first:
                for k in range(3):
                    for l in range(3):
                        DAC(x+k*n//3, y+l*n//3, n//3)
                return
            
    if first == -1:
        minusPaper += 1
    elif first == 0:
        zeroPaper += 1
    else:
        onePaper += 1

N = int(input())
papers = [list(map(int,input().split())) for _ in range(N)]
minusPaper, zeroPaper, onePaper = 0, 0, 0
DAC(0,0,N)
print(minusPaper, zeroPaper, onePaper, sep='\n')

1. 이 문제는 분할정복을 사용하여 해결할 수 있다. 분할정복은 DFS의 개념과 비슷하다.

2. 구간 안에서의 가장 첫 번째 종이 first를 기준으로 삼는다.

3. 반복을 하면서, 구간 안에서 first와 다른 종이가 발견되면, 다시 9등분으로 쪼개 탐색을 시작한다.

4. 탐색 완료, 즉 같은 종이들로만 이루어져있으면 first를 기준으로 minusPaper, zeroPaper,onePaper 에 더해준다.

5. 구간을 설정하는 것이 가장 헷갈리고 중요한 문제이다.

• 만약 문제가 4등분만 되어서 4사분면으로 쪼개진다면, 각각 적어주는 것이 직관적으로 좋을 수 있다.
• 그러나 이 문제는 3x3, 즉 9등분이기에 이중 for문을 활용해서 탐색을 반복해준다.

느낀 점 & 배운 점

1. 분할 정복 문제를 풀어보다 보니, 2x2나 3x3으로 주로 나오는 것 같다.
2. 전자에서는 4사분면으로, 후자에서는 이번 문제와 같이 코드를 작성해주는 것이 편할 듯하다.
3. 이제는 분할정복을 까먹지 말고 잘 풀어야겠다!!