[ 백준 ] 1780번 - 종이의 개수 (Python)

기본 정보

• Level: silver 2
• Problem Link: 종이의 개수
• Problem Number: 1780
• My Solution Link: 나의 풀이
• Algorithm I used: 분할정복(divide & conquer)

문제

• N×N 행렬 → 각 칸에는 -1, 0, 1 중 하나가 저장
• 행렬 자르는 규칙
  1. 모두 같은 수로 구성 → 그대로 사용
  2. 1이 아닌 경우 종이를 같은 크기의 종이 9개로 자르고, 각각 조각에 대해 1을 반복
• 최종적으로 만들어진 최소 크기의 조각들은 각각 크기가 다를 순 있다.
• 1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수?

알고리즘

• -1만 채워진 종이 수, 0만 채워진 종이 수, 1로만 채워진 종이 수 counting하는 변수
• 입력값 2차원 배열에 넣기
• 구성 숫자 동일성 검사
  • -1 vs. 0 vs. 1 확인해서 counting
  • 동일하지 않을 때 쪼개기 및 재귀
• 재귀할 경우 어떠한 정보를 전달하는가?
  • 각 분할 영역의 좌측상단 좌표
  • 새로운 n 크기

나의 풀이

• 막상 구현하려니 너무 막막해서 결국 구글링
• 근데 $O(n^4)$라서 complexity 측면에서 좋은 코드인지는 모르겠다.

N = int(input())

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

minus_ones, zeros, ones = 0,0,0

def dnc(r,c,n):
    """
    args
        - x, y : 각 구역의 좌측상단 좌표
        - n : 각 구역의 크기 (가로 길이)
    """

    global minus_ones, zeros, ones  # 재귀하므로 함수 내부에서 초기화 X

    standard = nums[r][c]  # 각 구역의 좌측상단 수 (기준 수)

    # 각 구역을 구성하는 숫자 체크 (linear search)
    for i in range(r,r+n):
        for j in range(c,c+n):
            if nums[i][j] != standard:  # 현재 구역이 두 가지 이상의 수로 구성된 경우
                new_n = n // 3  # 가로(세로)당 1/3배씩
                for a in range(3):
                    for b in range(3):
                        new_r, new_c = r + (new_n * a), c + (new_n * b)  # 분할될 각 구역의 좌측상단 좌표
                        dnc(new_r,new_c,new_n)  # 분할될 각 구역에 대해 재귀 (동일성 검사)
                return  # 왜 여기다가?

    # 해당 구역이 동일한 수로 구성된 경우 counting
    if standard == -1:
        minus_ones += 1
    elif standard == 0:
        zeros += 1
    else:
        ones += 1

dnc(0,0,N)
print(f'{minus_ones}\n{zeros}\n{ones}')