[CLASS 3]백준 2630번 - 색종이 만들기

2630번 : 색종이 만들기

 

기초적인 분할 정복 문제라고 할 수 있겠다. 큰 사각형부터 시작해서 조건이 맞지 않는다면 작은 사각형 4개로 나누는 과정을 반복하여 해결할 수 있다. 재귀함수로 구현할 수 있다.

 

내 코드:

import sys
input = sys.stdin.readline
n = int(input())
p = [list(map(int,input().split())) for _ in range(n)]
zero = 0
one = 0

def find(y,x,n):
    global zero,one

    temp = p[y][x]
    for ty in range(y,y+n):
        for tx in range(x,x+n):
            if temp != p[ty][tx]:
                find(y,x,n//2)
                find(y,x+n//2,n//2)
                find(y+n//2,x,n//2)
                find(y+n//2,x+n//2,n//2)
                return

    if temp == 0:
        zero += 1
    else:
        one += 1

find(0,0,n)
print(zero)
print(one)

매개변수로 왼쪽 위 점의 좌표와 검사할 길이 n을 받는다. 이후 temp변수에 왼쪽 위 값을 저장하고 for문을 통해 다른 점들을 차례차례 검사한다. 만약 왼쪽 위와 다른 값을 가진 점이 한 곳이라도 나왔다면 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래를 기준으로 검사 영역을 1/4 로 줄여서 다시 검사한다. 이렇게 되면 검사 영역의 값들이 모두 같을 때까지 검사 영역이 좁혀지고, 그 영역이 하나의 색종이 조각이 된다.

 

재귀는 짜고나면 참 간단하고 명료한데 짜는 과정이 참 머리가 아픈 것 같다. 머리도 같이 짜는 느낌?