백준 2630 풀이 (색종이 만들기, 쿼드트리, 분할정복, 파이썬)

이 문제는 크게 어렵지는 않았다. 예전에 재귀를 처음 다뤘을때가 생각이 났다. 약 한달전이었지 그때 정말 재귀가 너무 어려워서 마치 재귀란 도대체 왜 이렇게 어려운지 마귀의 친구인가 했던.....

여튼 문제는 간단하다. 종이가 있는데 이 종이를 4분면씩 잘라서 전부 1이나 0이면 카운트를 하나씩 증가 시켜서 1종이, 0종이의 개수를 구하면 되는 것이다.

그럼 생각해보자.

우선 전부 통일된 숫자인지 파악해야한다. 만약 통일되지 않으면 4분면으로 잘라서 전부 통일된 숫자인지 파악해야한다. 만약 통일되지 않으면 4분면으로 잘라서 통일된 숫자인지 파악해야한다. 만약 통일되지 않으면 4분면.......딱 봐도 재귀다.

그래서 재귀함수를 대충 짜주면 된다.

 

이번에 귀찮았던것은 numpy를 쓰지 않고 4분면으로 자르려니 살짝 고민해버렸다. numpy를 쓰면 원하는 위치를 잘라낼수 있는데 실제 코테에서는 python의 내장함수만 쓸 수 있도록 허용하다보니 numpy를 못쓰는 경우도 존재한다. 그래서 이번에는 numpy없이 일일히 잘라주는걸 짜다보니 살짝 고민을 해버린 것이다.

 

그래서 코드를 짜본 결과 아래와 같다. 

import sys
n = int(sys.stdin.readline())

n0 = 0
n1 = 0
def check(p):
    global n0
    global n1
    f = p[0][0]
    wrong = 0
    for i in range(len(p)):
        for j in p[i]:
            if f != j:
                wrong = 1
                break
        if wrong == 1:
            break
    if wrong == 1:#중간에 노이즈 있으므로 나눠줘야함.
        a=[] # 절반, 절반
        b=[]
        c=[]
        d=[]
        for i in range(len(p)//2):
            a.append(p[i][:len(p)//2])
            b.append(p[i][len(p)//2:])
        for i in range(len(p)//2,len(p)):
            c.append(p[i][:len(p)//2])
            d.append(p[i][len(p)//2:])
        check(a)
        check(b)
        check(c)
        check(d)
    else:
        if f == 0:
            n0 += 1
        else:
            n1 += 1
p = []
for _ in range(n):
    p.append(list(map(int, sys.stdin.readline().split())))
check(p)

print(n0)
print(n1)

 

 

이 문제를 쿼드트리라고 설명은 해 놓았는데. 그냥 재귀만 풀어본 사람도 충분히 풀 수 있는 문제 였던거 같다.