[백준/1780/파이썬] 종이의 개수

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

1780번: 종이의 개수

Problem

• N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.
• 아래의 조건과 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오

조건

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

SOL

딱봐도, 재귀적인 구조로 이루어져 있는 문제이다. 그리고, 큰 문제를 작은 문제로 쪼개서 푸는 분할정복의 대표적인 예시인거 같다.

분할정복은 개념자체는 간단하지만, 구현을 하기가 참 까다로운 문제이다. 문제의 Flow chart를 정확하게 이해를 해야, 반복을 몇번 할지 / 탈출은 언제 해줄지 / 어떤식으로 반복할지 등을 정할 수 있다.

 

우선, 입력이 3^k이기 때문에, 매번 9개로 정확히 나눌 수 있기 때문에, 이 부분에 대해서는 신경을 쓰지 않아도 된다.

반복을 몇번 해야할까?

조건 (1)에 의해서, 종이가 모두 같은 수로 되어있는지 확인을 해야한다. 즉, 반복을 "N^2"만큼 하는건 자명한 사실일거 같다. 하지만, 종이가 같은 수로 되어있지 않다면 -> 2번 조건으로 가야한다. 아래와 같이 Psudo Code를 만들 수 있을거다.

## Psudo Code 
def solve(y,x,n):
   	zero, one,minus_one
    init == 비교 대상 
	init = borad[y][x]
	if 모두 같은걸로 이루어져 있다면:
    	pass
    else:
       9개로 나눠야한다.
    
    if init ==0 :
     	zero+=1..

여기서, 종이를 9개로 자르는걸 어떻게 구현할 지 고민을 해야한다. 사실 이게 이 문제의 핵심인거 같다. 

9개로 자른다 !?

오른쪽과 같이 9*9 배열이 주어졌다고 생각해보자. 이제 indexing을 잘 해야할거 같은데, 어떤식으로 indexing이 되는지 규칙을 찾는게 우리가 할 일이다. 

 

* For 문을 이용해서 배열을 탐색할 때는, Left to Right로 반복을 한다. 그걸 유념하고 , 반복을 어떻게 해줄지 살펴보자.(why ? 배열을 선언을 하면, Left to Right로 연속된 메모리 공간이 잡힌다. 우리가 그걸 2차원,3차원의 개념을 논리적으로 부여할뿐, 컴퓨터에는 연속된 공간이 있을 뿐이다.)

 

Flow chart 

위의 예시로 생각을 해보자.

 

처음에는 N=9인 9*9의 배열을 탐색하기 시작할거다. 반복문을 돌때, 선형적으로 반복을 한다고 하면, 아래와 같은 순서로 반복을 하게 된다.

compare board[0][0],board[0][1]

comepare board[0][1], board[0][2] ..

하지만, board[0][1]과 board[0][2]는 다르기 때문에, 이 조각은 더 작은 조각으로 나눠서 살펴봐야한다.

 

그럼 우리는, 시작점이 각각 [0][0] ,[0][3],[0][6] , [3][0],[3][3],[3][6],[6][0],[6][3],[6][6]인 크기가 3*3인 조각으로 나눠야 살펴봐야 할거다. 아래와 같이 말이다.

즉, 크기는 처음보다 3으로 나눈 값만큼 작아지고, 시작점들은 여러개가 생기게 된다.

시작점을 어떻게 정해줄까? 위의 의사코드를 갖고와서 코드를 보면서 생각해보자.

## Psudo Code 
def solve(y,x,n):
   	zero, one,minus_one
    init == 비교 대상 
	init = borad[y][x]
	if 모두 같은걸로 이루어져 있다면:
    	pass
    else:
       9개로 나눠야한다.
    
    if init ==0 :
     	zero+=1..

우리가 지금 Branch(분기)가 발생한 지점이 board[0][1]과 board[0][2] 지점에서 발생했고, 이 지점에서 y,x는 각각 0일거다. 왜냐하면, 처음 반복을 하는거니까 당연히 0,0 부터 시작을하기 때문이다.

 

그러면, 이제 우리는 똑같은 논리를 계속 재활용을 해야하기 때문에, 재귀함수를 이용할거다. 왜냐하면, 답을 구하는데 논리가 바뀌지 않기 때문이다. 나라면 아래와 같이 구현해줄거다.

이때 중요한게, 일반화된 식을 적어야한다는 것이다. 

3번, 0,3,6을 더한다고해서, y+k*3 이런식으로 정적인 값으로 적어주면 안된다. 크기에 따라서 유동적으로 값이 변하기 때문에, 크기 값을 넣어줘야한다.

for k in range(3):
	for l in range(3):
    	solve(y+k*n//3,x+l*n//3,n//3)

 

즉 9개로 나누는 코드를 완성시키면 이런 느낌이 될거다.

def solve(y,x,n):
    global zero,one,minus_one
    # 종이가 모두 같은 수로 이루어져 있는지 확인
    init=board[y][x]
    for i in range(y,y+n):
        for j in range(x,x+n):
            if board[i][j] != init:
                # 같은 수로 이루어져 있지 않다면, 9 등분을 합시다.
                for k in range(3):
                    for l in range(3):
                        solve(y+k*n//3,x+l*n//3,n//3)

재귀함수에서 재귀의 로직을 짜는것만큼 중요한게 종료시점이다.

 

언제 종료를 해줘야할까? board[i][j]와 board[i][j-1] 가 다른 순간, 우리는 그 반복을 더 수행할 필요가 있을까? 

예를들어, board[0][1]과 board[0][2]가 다른데, board[0][2]와 board[0][3]이 다른지 아닌지 확인할 필요가 있을까? 

답은 NO다.

그러니까, 재귀함수를 call해주고, call 해주기 전의 함수는 return으로 종료를 해줘야한다.

즉, 코드로 표현하면 이중반복이 끝나는 시점(재귀함수를 모두 부른 시점)

def solve(y,x,n):
    global zero,one,minus_one
    # 종이가 모두 같은 수로 이루어져 있는지 확인
    init=board[y][x]
    for i in range(y,y+n):
        for j in range(x,x+n):
            if board[i][j] != init:
                # 같은 수로 이루어져 있지 않다면, 9 등분을 합시다.
                for k in range(3):
                    for l in range(3):
                        solve(y+k*n//3,x+l*n//3,n//3)
                # 같지 않기 때문에, 이 loop는 종료해줍니다. 불필요한 반복을 하지 않습니다.
                return

 

완성된 코드

# 분할정복
# divide Conquer
import sys
sys.setrecursionlimit(10**6)
input= sys.stdin.readline

N=int(input().rstrip())

board=[list(map(int,input().split())) for _ in range(N)]
zero=0
one=0
minus_one=0
def solve(y,x,n):
    global zero,one,minus_one
    # 종이가 모두 같은 수로 이루어져 있는지 확인
    init=board[y][x]
    for i in range(y,y+n):
        for j in range(x,x+n):
            if board[i][j] != init:
                # 같은 수로 이루어져 있지 않다면, 9 등분을 합시다.
                for k in range(3):
                    for l in range(3):
                        solve(y+k*n//3,x+l*n//3,n//3)
                # 같지 않기 때문에, 이 loop는 종료해줍니다. 불필요한 반복을 하지 않습니다.
                return
    if init==0:
        zero+=1
    elif init==1:
        one+=1
    elif init==-1:
        minus_one+=1
    return

solve(0,0,N)

print(minus_one)
print(zero)
print(one)