[Baekjoon] 1780. 종이의 개수

문제 설명

문제

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

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

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

입력

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

출력

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

예제 입력 1

9
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
0 1 -1 0 1 -1 0 1 -1
0 -1 1 0 1 -1 0 1 -1
0 1 -1 1 0 -1 0 1 -1

예제 출력 1

10
12
11

문제 풀이

# 분할정복

이 문제는 백준 2630. 색종이 만들기와 유사한 문제입니다.

다만, 입력의 크기가 훨씬 커지고 분할 개수 또한 증가하였습니다.

따라서, 아래와 같은 풀이로는 시간초과를 피할 수 없습니다.

👍 1번 풀이: 시간 초과

def count_paper(N, papers, cnt):
    isPaper = True if sum([papers[0][0] == p for l in papers for p in l]) == N**2 else False
    if isPaper:
        if papers[0][0] == -1: return [1,0,0]
        if papers[0][0] == 0: return [0,1,0]
        if papers[0][0] == 1: return [0,0,1]
    else:
        return [sum(cnts) for cnts in zip(*[count_paper(N//3, [l[(N//3)*j:(N//3)*(j+1)] for l in papers[(N//3)*i:(N//3)*(i+1)]],cnt)
                                            for i in range(3) for j in range(3)])]


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

위 코드는 papers라는 큰 크기의 리스트를 계속해서 복제하고, 가지고 다니기 때문에 시간이 오래 걸릴 수 밖에 없습니다.

따라서 이러한 경우, 탐색할 인덱스만을 전달하는 방법을 이용하여 해결할 수 있습니다.

👍 2번 풀이: 6072ms

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

def count_papers(N,row,col):
    global ans
    first = papers[row][col]
    for i in range(row,row+N):
        for j in range(col,col+N):
            if first != papers[i][j]: break
        else: continue
        break
    else: # 모두 같은 종이일 때
        ans[first+1] += 1
        return
    # 다른 종이가 있을 때
    for i in range(3):
        for j in range(3):
            count_papers(N//3,row + N//3*i,col + N//3*j)
    return

count_papers(N,0,0)
print(*ans,sep='\n')

첫번째 코드와 비교하면 크게 세 부분이 변했습니다.

1. papers 인자를 들고 다니지 않습니다.

저는 재귀함수에서 인자가 계속해서 전달되는 것을 해당 인자를 들고 다닌다고 표현을 하는데, papers 2차원 리스트를 들고 다니는 대신 탐색할 시작 위치와 범위만 전달합니다.

2. cnt도 들고 다니지 않습니다.

이 부분에서 크게 차이가 생기는지 실험해보지는 않았는데, cnt를 들고 다니는 것도 연산에 부하를 초래할 수 있다고 생각해서 전역 변수로 설정했습니다.

3. 종이가 모두 같은지 비교할 때 전부 탐색하지는 않습니다.

첫번째 코드는 해당 범위의 종이들을 전부 탐색해서 모두 같은지 검사합니다.

하지만 두번째 코드에서는 다른 종이가 나오면 바로 break합니다.

사전에 break하지 않고 전체를 탐색하게 되면 또 다시 시간 초과가 발생합니다.