[파이썬] 백준 2630 : 색종이 만들기

[파이썬] 백준 2630 : 색종이 만들기

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

2630번: 색종이 만들기

실버 3

분할정복, 재귀

---

분할정복에서 가장 기본적인 문제라고 한다.

 

문제에서 4등분을 범위를 어떻게 잡아야하는지 친절하게 알려주고 있었다.

 

종이들을 2차원 리스트로 입력받도록 하고, 각각의 값들을 돌면서 모두가 통일된 값을 가지고 있는지 확인해야 한다.

각 사각형의 제일 왼쪽 위를 기준점으로 잡고, 나머지 값들이 기준점의 값과 같지 않다면 한번 더 네 등분을 해야한다.

이는 재귀함수를 반복적으로 적용하는 방법으로 구현할 수 있었다.

 

코드

import sys
N = int(sys.stdin.readline())
paper = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
white, blue = 0, 0    # 흰색, 파란색 종이가 몇 개인지 저장함
def solution(x, y, N):    # 4등분하는 함수
    global white    # 전역변수를 얻어옴
    global blue
    color = paper[x][y]    # 사각형의 가장 왼쪽위를 기준점으로 함. 0이면 흰색, 1이면 파란색
    for i in range(x, x+N):    # 이중 for문으로 2차원 리스트를 전부 순회함
        for j in range(y, y+N):
            if color != paper[i][j]:    # 기준점의 값과 다른 부분이 사각형내에 존재한다면 4등분
                solution(x, y, N//2)    # 2사분면 : 기준점은 유지하고 범위를 반으로 줄임
                solution(x+N//2, y, N//2)    # 1사분면 : x의 시작값을 N//2만큼 늘림
                solution(x, y+N//2, N//2)    # 3사분면 : y의 시작값을 N//2만큼 늘림
                solution(x+N//2, y+N//2, N//2)    # 4사분면 : x, y시작값을 N//2만큼 늘림
                return    # 더이상 쪼갤 수 없을만큼 쪼갰으므로 함수를 종료함
    
    if color == 0:    # 기준점의 색과 다른부분이 없으므로 더 쪼갤 필요가 없음. 기준점 색이 곧 색종이의 색과 같음
        white += 1
    else:
        blue += 1

solution(0, 0, N)
print(white)
print(blue)

 

 

분할정복과 DP는 문제를 잘개 쪼개서 가장 작은 단위로 분할한다는 공통점이 있으며,

DP는 부분 문제가 중복되고 상위 문제 해결시 재활용할 수 있는 메모이제이션 기법을 사용하지만

분할정복은 부분 문제 중복이 없고 메모이제이션 기법을 사용하지 않는다는 차이점이 있다.