[Python] BOJ 2630 - 색종이 만들기(분할 정복)
https://www.acmicpc.net/problem/2630
2630번: 색종이 만들기
첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.
www.acmicpc.net
* 분할 정복이란?
- 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법
분할 정복에도 여러가지 종류가 있지만, 이 문제는 쿼드트리(quad-tree)를 통해 풀어 보았다.
(https://www.acmicpc.net/problem/1992 백준에는 쿼드트리 문제도 있지만, 이 문제가 더 쉽다)
import sys input = sys.stdin.readline n = int(input()) Map,line = [],[] blue,white = 0,0 for i in range(n): Map.append(list(map(int,input().split()))) def quad_tree(n,x,y): global blue global white color = Map[x][y] for i in range(x,x+n): for j in range(y,y+n): if(Map[i][j] != color): color = -1 break if(color == -1): break if(color == 0): white += 1 elif(color == 1): blue += 1 elif(color == -1): quad_tree(n//2,x,y) quad_tree(n//2,n//2+x,y) quad_tree(n//2,x,n//2+y) quad_tree(n//2,n//2+x,n//2+y) quad_tree(n,0,0) print(white) print(blue)
기준값인 Color를 Map[x][y]로 설정하고 n x n 크기의 정사각형만큼의 범위를 이중for문으로 체크하면서 Map[x][y]와 기준값이 같은지 확인해서 하나라도 다르면 color에 -1을 넣고 break를 걸어주었다.
모두 같으면 color가 모두 1이거나 0이므로 white나 blue에 1을 더해주었고 color가 -1이면 Map을 4분할한다음 각 사분면마다 재귀함수로 quad_tree함수를 실행시켜주었다.
* 예제입력과 같은경우에는 n이 8이므로 처음에 Map[0][0]부터 Map[7][7]까지 확인해서 1과 다른 칸이 하나이상 있으므로 color에 -1을 넣고 quad_tree(4,0,0), quad_tree(4,4,0), quad_tree(4,0,4), quad_tree(4,4,4)를 실행한다. 그 뒤로는 이와 같다.