[Silver II] 종이의 개수 - 1780

문제 링크

성능 요약

메모리: 369804 KB, 시간: 2744 ms

분류

분할 정복, 재귀

문제 설명

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

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

입력

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

출력

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

---

풀이

아이디어

문제에서 예시로 준 데이터를보면 위 그림과 같이 0의 개수를 센다.
우선 찾을 정사각형의 가장 왼쪽 x,y 좌표를 찾은 뒤, 탐색하는 정사각형의 크기 N만큼 탐색하여 다른것이 있다면 재귀, 모두 같다면 cnt의 알맞는 인덱스에 집어넣어 개수를 세는 방식이다.

코드

import sys
input = sys.stdin.readline
cnt = [0, 0, 0]

N = int(input())
paper = [list(map(int, input().split())) for _ in range(N)]

def conquer(x, y, n):
    lst = [paper[i][y:y+n] for i in range(x, x+n)]
    if len(set(k:=sum(lst, []))) == 1:
        cnt[k[0]] += 1
        return

    d = n // 3
    for i in range(0, n, d):
        for j in range(0, n, d):
            conquer(x+i, y+j, d)


conquer(0, 0, N)
print(cnt[-1])
print(cnt[0])
print(cnt[1])

---

회고

문제풀이하는데 시간이 너무 오래 걸렸고, 재귀적인 방법을 머리속으로 구현하는데도 오래걸렸다.
또한 위 코드 같은 경우, 입력 최댓값에, 가장 큰 정사각형의 크기가 1 인경우 시간복잡도가 $O(N^2)$이 되어 시간초과가 발생하는데, 이로인해서 python으로 제출시 WA가 발생한다.

DFS도 재귀적인 방법이므로 DFS를 사용할 수 도 있을것 같다.