[백준] 1780. 종이의 개수

김규민·2025년 5월 16일

백준

알고리즘 문제풀이

목록 보기

11/13

종이의 개수

배경 아이디어

문제의 지문을 통해 재귀적으로 구현해야 하는 부분에 대해 파악하기 쉽습니다.

현재 종이가 모두 같은 숫자로 구성되어 있는지 확인한다.
그렇다면 구성된 숫자의 카운트를 증가한다.
아니라면 종이를 9등분하여 1, 2번을 반복한다.

재귀적인 기능을 도출하는 것은 수월한 편이지만, 각 기능을 구현하는 방법을 도출하는 과정이 까다로울 수 있습니다.

1. 현재 종이가 모두 같은 숫자로 구성되어 있는지 확인한다

set 함수를 이용한 숫자 확인
-1, 0, 1 중 한 가지 숫자로 구성되어 있는 것을 확인하기 위해 활용할 수 있는 방법으로 가장 먼저 생각한 것은 set() 함수를 활용하는 것이다.

입력받은 2차원 배열을 set 을 통해 중복된 값을 제거하면 한 가지 숫자로 구성되어 있고, 해당 숫자의 종류까지 파악할 수 있어 효율적이라고 판단했다.

하지만, set 함수는 1차원 배열에 대해서만 사용 가능하여 입력에 대해 직접 사용할 수 없다는 한계가 존재한다.

종이의 첫번째 값과 나머지 값 비교
종잇조각의 첫 번째 칸의 숫자와 나머지 칸의 숫자를 비교하여 해당 조각의 숫자가 모두 같은 것을 판단할 수 있다.

비효율적이라고 생각했지만, set 함수의 한계를 극복하는 것보다 효과적인 방법이라고 생각하여 채택하게 되었다.

2. 그렇다면 구성된 숫자의 카운트를 증가한다
재귀 함수의 내부에서 출력값을 저장하면 혼동의 위험이 있기 때문에 -1, 0, 1 각각의 종이 개수를 셀 수 있는 딕셔너리를 선언했다.

1번 작업에서 종이의 모든 숫자가 동일하다면 변수에 저장했던 첫 번째 숫자를 딕셔너리의 키로 하여 개수를 증가시킨다.

3. 아니라면 종이를 9등분하여 1, 2번을 반복한다

1074번 Z 문제에서는 특정 좌표의 위치를 사분면 중에서 탐색하는 사분탐색과 같은 방식이었다면,
이 문제는 탐색이 아니라 9번을 실행해야 한다는 차이점이 있다.

이중 for 문을 사용해 종이를 9등분하는 종이의 크기와 좌표를 생성한다.
재귀 함수에 전달하여 각 9등분된 종이에 대해 판별을 계속한다.

코드

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

result = {-1: 0, 0: 0, 1: 0}

def count(x, y, size):
    first = paper[x][y]
    same = True
    for i in range(x, x + size):
        for j in range(y, y + size):
            if paper[i][j] != first:
                same = False
                break
        if not same:
            break
    
    if same:
        result[first] += 1
    else:
        new_size = size // 3
        for dx in range(3):
            for dy in range(3):
                count(x + dx * new_size, y + dy * new_size, new_size)

count(0, 0, N)
print(result[-1])
print(result[0])
print(result[1])