[백준 1780] 종이의 개수

문제

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로만 채워진 종이의 개수를 출력한다.

---

접근

가장 큰 NxN크기의 종이를 판별하고 같은 수로 이루어지지 않았을 때 3등분을 한다.

이 문제에서 NxN이 같은 수로 되어있는 것을 어떻게 판별 할 것인지?

3등분을 어떻게 할 것인지를 생각해야한다.

 

먼저 같은 수로 구성되어있는 것을 확인하기 위해서는 NxN에서 가장 좌상단에 있는 수와 다른 위치에 있는 수들을 비교한다. 다를 때는 3등분을 하게된다.

 

구현

종이의 크기 N을 입력받고 종이의 정보를 paper에 저장한다.

그리고 최종적으로 출력할 해를 answer에 저장한다.

 

종이의 개수를 알아보기위해 재귀함수를 활용하고 처음에는 (0, 0)부터 시작하여 NxN크기를 모두 탐색한다.

N = int(input())
paper = [list(map(int ,input().split())) for _ in range(N)]
answer = [0, 0, 0] # -1, 0, 1

cut_paper(0, 0, N)

 

기본적으로 재귀함수를 통해 문제를 해결하고 가장 처음에 입력받은 (cy, cx)에 있는 수를 다른 위치의 수와 비교하기위해 check에 넣는다.

2차원 리스트를 탐색하며 다른 수가 있는지 확인하고 다른 수가 있다면 (cy, cx)를 기준으로 3등분을 한다.

만약 해당 크기의 종이가 모두 같은 수라면 return이 되지않고 아래 각 종이의 정보에 따라 해를 증가시킨다.

def cut_paper(cy, cx, n):
    global answer
    check = paper[cy][cx]
    for y in range(cy, cy+n):
        for x in range(cx, cx+n):
            if check != paper[y][x]:
                for i in range(3):
                    for j in range(3):
                        cut_paper(cy+n//3*i, cx+n//3*j, n//3)
                return

    if check == -1:
        answer[0] += 1
    elif check == 0:
        answer[1] += 1
    elif check == 1:
        answer[2] += 1

---

전체 코드

import sys
input = sys.stdin.readline
def cut_paper(cy, cx, n):
    global answer
    check = paper[cy][cx]
    for y in range(cy, cy+n):
        for x in range(cx, cx+n):
            if check != paper[y][x]:
                for i in range(3):
                    for j in range(3):
                        cut_paper(cy+n//3*i, cx+n//3*j, n//3)
                return

    if check == -1:
        answer[0] += 1
    elif check == 0:
        answer[1] += 1
    elif check == 1:
        answer[2] += 1

N = int(input())
paper = [list(map(int ,input().split())) for _ in range(N)]
answer = [0, 0, 0] # -1, 0, 1

cut_paper(0, 0, N)
for i in range(3):
    print(answer[i])