[BOJ/백준] 2630번 색종이 만들기 | 분할정복 | 파이썬

문제

 

풀이

import sys

def cutPaper(x, y, n):  # x,y좌표와 색종이 크기 
    global cnt_white, cnt_blue
    print(x, y, n)
    for i in range(x, x+n):
        for j in range(y, y+n):
            if paper[x][y] != paper[i][j]:
                cutPaper(x, y, n//2)
                cutPaper(x, y+n//2, n//2)
                cutPaper(x+n//2, y, n//2)
                cutPaper(x+n//2, y+n//2, n//2)
                return # 호출한 함수는 중복되지 않도록 종료시킴

    if paper[x][y] == 1:
        cnt_blue += 1
    else:
        cnt_white += 1

n = int(input())
paper = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

cnt_white, cnt_blue = 0, 0
cutPaper(0,0,n)
print(cnt_white)
print(cnt_blue)

 

문제를 작은 문제로 분할하여 해결하는 분할정복(Divide and conquer) 문제.

 

문제에 가장 핵심적인 부분은 다음과 같다.

 

전체 종이가 모두 같은 색으로 칠해져 있지 않은 경우 똑같은 크기의 네 개 색종이로 나눠야 한다.

• for문을 사용해서 모든 위치의 색이 같은지 확인한다.
• 만약 색이 다른 경우 n을 n//2로 바꿔 4개의 함수를 호출한다.

그림으로 나타내면 다음과 같다.

 

 

• 색종이의 크기 n과(n x n) 색상을 나타내는 2차원 배열 paper를 입력 받았다.
• 흰색 색종이의 수와 파란색 색종이의 개수를 세는 cnt_white, cnt_blue 변수를 0으로 초기화했다.
• 색종이를 더 이상 자를 수 없을 때 까지 네 개의 색종이로 나누는 함수 cutPaper를 만들었다.

 

 

풀이 방법을 한 번에 생각해내기 어려워서 다른 사람들의 도움을 받았다. 

 

처음에는 return의 위치가 잘 이해되지 않았는데 2x2 색종이 예시를 실행시켜 본 후 이해했다.

색이 다른 경우 함수 4개를 호출시키고 return을 사용해야 중복을 방지할 수 있다😇

 

---

백준 2630번 :색종이 만들기

2630번: 색종이 만들기