[알고리즘] 백준 1780 종이의 개수 (파이썬 풀이)

https://www.acmicpc.net/problem/1780

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

 

해결코드

n = int(input())

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

minus = 0
zero = 0
plus = 0

def num(x,y,n):
    global minus, zero, plus
    cnt = li[x][y]
    for i in range(x,x+n):
        for j in range(y, y+n):
            if li[i][j] != cnt:
                num(x,y,n//3)
                num(x,y+n//3,n//3)
                num(x,y+(n//3)*2,n//3)
                num(x+n//3,y,n//3)
                num(x+n//3,y+n//3,n//3)
                num(x+n//3,y+(n//3)*2, n//3)
                num(x+(n//3)*2,y,n//3)
                num(x+(n//3)*2,y+n//3,n//3)
                num(x+(n//3)*2,y+(n//3)*2,n//3)
                return
    if cnt== -1:
        minus += 1      
    elif cnt == 0:
        zero += 1        
    else:
        plus += 1   
num(0,0,n)
print(minus)
print(zero)
print(plus)

문제풀이

저번에 풀었던 분할정복 문제와 거의 유사하다.

지난번 색종이 문제는 두가지 경우라 4분할로 풀었고, 이번 문제는 세가지 경우라 9분할을

적용하여 풀면 된다.

 

코드를 보자

 

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

줄 개수 n을 입력받아주고

리스트에 n개의 줄에 종이에 적힌 n개의 숫자를 입력받아 li에 넣어준다.

 

minus = 0
zero = 0
plus = 0

-1,0,1 총 세가지 경우가 있으므로 각각의 변수를 선언해주고 0으로 초기화해준다.

 

def num(x,y,n):
    global minus, zero, plus
    cnt = li[x][y]

num함수를 보자

전에 선언한 minus, zero, plus 변수를 전역변수로 가져온다.

그리고 cnt라는 변수에 li리스트 원소를 넣는다(첫 시작은 무조건 0,0으로 한다)

    for i in range(x,x+n):
        for j in range(y, y+n):
            if li[i][j] != cnt:
                num(x,y,n//3)
                num(x,y+n//3,n//3)
                num(x,y+(n//3)*2,n//3)
                num(x+n//3,y,n//3)
                num(x+n//3,y+n//3,n//3)
                num(x+n//3,y+(n//3)*2, n//3)
                num(x+(n//3)*2,y,n//3)
                num(x+(n//3)*2,y+n//3,n//3)
                num(x+(n//3)*2,y+(n//3)*2,n//3)
                return

이차원 for문을 돌려서 li리스트의 원소들을 확인해준다.

만약 하나라도 cnt값과 같지 않다면 종이를 9개로 쪼개줘야 한다.

쪼갤때는 (0,0)을 기준으로 1~9사분면까지 만들어서 재귀해준다.

 

if cnt== -1:
        minus += 1      
    elif cnt == 0:
        zero += 1        
    else:
        plus += 1   

cnt값에 따라 각각의 변수에 +1을 해준다.

 

num(0,0,n)
print(minus)
print(zero)
print(plus)

num함수를 실행시킨다.(시작 좌표 0,0)

차례대로 결과들을 출력해준다.