[python]백준 1780번 : 종이의 개수

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256 MB	9503	5463	4173	58.667%

문제

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

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

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

입력

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

출력

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

나의 답

첫번째 코드

def returnArea(arr,value,size):
    tmp_arr = list()
    for i in range(0,size//3):
        tmp = list()
        for j in range(0,size//3):
            tmp.append(arr[i+(value//3)*(size//3)][j+((value%3)*(size//3))])
        tmp_arr.append(tmp)
    return tmp_arr

def calPaperNum(size,num_arr,arr):
    first_v = arr[0][0]
    tmp = 0
    for i in range(0,size): # n
        for j in range(0,size): # n
            if not(first_v == arr[i][j]):
                tmp = 1
                for k in range(0,9): # 9 
                    area = returnArea(arr,k,size)
                    num_arr = calPaperNum(size//3,num_arr,area)
                return num_arr
    # n^(2logn)
    if not(tmp):
        num_arr[first_v+1]+=1
        return num_arr

우선 이전에 풀었던 방식대로 구성을 해보았다. 주어진 array를 돌면서 다른 부분이 발견되면 returnArea라는 함수에서 9등분으로 쪼개진 array를 return 받아 하나씩 다시 재귀로 돌리는 방식이다. 여기서 시간 복잡도는 n^(2logn)이 나왔는데, 이는 주어진 제한조건을 훨씬 뛰어넘는다.

여기서 이전 '쿼드 트리' 문제부터 잘못 이해했다는 걸 알 수 있다. 분할 정복을 이용해야 복잡도를 줄일 수 있는 문제인데 계속 완전탐색으로 구현하려 했던 것이다.

두번째 코드

def calPaperNum(size,num_arr,arr):
    first_v = arr[0][0]
    tmp = 0
    for i in range(0,size): # n
        for j in range(0,size): # n
            if not(first_v == arr[i][j]):
                tmp = 1
                break
        if tmp:
            break
    if not(tmp):
        num_arr[first_v+1]+=1
        return num_arr
    else:
        for k in range(0,9): # 9 
            area = returnArea(arr,k,size)
            num_arr = calPaperNum(size//3,num_arr,area)
        return num_arr

for문 내에 재귀가 있어서 복잡도가 커지는가해서 밖에 위치시켜보았지만, 어차피 재귀에 들어가서 반복문을 또 실행하는 점은 같으므로 개선이 없었다.

최종 코드

import operator

line = int(input())
paper_arr = list()

for i in range(0,line):
    paper_arr.append(list(map(int,input().split())))

def calPaperNum(size,type_arr,num_arr,arr,sx,sy):
    start_y = sy+(type_arr//3)*(size)
    start_x = sx+(type_arr%3)*(size)
    first_v = arr[start_y][start_x]
    tmp = 0
    for i in range(start_y,start_y+size): # n
        for j in range(start_x,start_x+size): # n
            if not(first_v == arr[i][j]):
                tmp = 1
                break
        if tmp:
            break
    if not(tmp):
        num_arr[first_v+1]+=1
        return num_arr
    else:
        for k in range(0,9):
            num_arr = calPaperNum(size//3,k,num_arr,arr,start_x,start_y)
        return num_arr
    # O(n^2)
for obj in calPaperNum(line,0,[0,0,0],paper_arr,0,0):
    print(obj)

결국 이해하기 쉽게 만들려고 함수로 바꾸었던 것들이 해가 되어 돌아왔다. 불필요한 함수를 줄이고 for문이 최대한 겹치지 않게 두니 이와 같은 형태가 나왔다. returnArea 함수는 그 자체만으로 2중 for문을 가지고 있으므로 이를 사용하는 대신에 재귀함수로 넘어왔을 때 주어진 매개변수로 범위를 표현하기로 했다. 즉, 쪼개진 array를 따로 저장하고 계산할 필요없이, 주어진 array 자체에서 현재 계산할 array의 범위를 표현하는 방식으로 바꾸었다.

이런 식으로 표현하니 겹치는 for문이 줄고 시간 복잡도도 줄었지만 백준 기준으로 66876KB의 메모리와 7004ms의 시간이 걸렸다. python 코드 중 4000ms 즈음으로 복잡도를 줄인 코드가 있으니 다른 방법을 더 생각해봐야할 것 같다.

 

배운 것

• for문은 최대한 적게 쓰도록 할 것
• 복잡도를 줄이기 위해서는 기능 모듈화를 줄일 것