Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

20. 분할 정복

재귀를 응용하는 알고리즘, 분할 정복을 익혀 봅시다.

Java / Python

1. 색종이 만들기

2630번

쿼드트리를 만드는 문제

이번 문제는 정사각형 모양의 종이를 일정한 규칙에 따라 잘라 다양한 크기를 가진 하얀색 또는 파란색 색종이를 만드는 문제입니다. 정사각형으로 4등분씩 분할하면서 해당 파티션 내의 색상이 동일한 지 확인하는 방식으로 작성했습니다.

• Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int white = 0;
	public static int blue = 0;
	public static int[][] board;
 
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());	
		board = new int[N][N];
        
  		StringTokenizer st;
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			
			for(int j = 0; j < N; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		partition(0, 0, N);
		
		System.out.println(white);
		System.out.println(blue);
		
	}
	
	public static void partition(int row, int col, int size) {
		
		if(colorCheck(row, col, size)) {
			if(board[row][col] == 0) {
				white++;
			}
			else {
				blue++;
			}
			return;
		}
		
		int newSize = size / 2;
		// 재귀 호출
		partition(row, col, newSize);	// 2사분면
		partition(row, col + newSize, newSize);	// 1사분면
		partition(row + newSize, col, newSize);	// 3사분면
		partition(row + newSize, col + newSize, newSize);	// 4사분면
	}
	
	// 현재 파티션의 색상이 같은지 확인
	public static boolean colorCheck(int row, int col, int size) {
	
		int color = board[row][col];	// 첫 번째 원소 기준
		
		for(int i = row; i < row + size; i++) {
			for(int j = col; j < col + size; j++) {
				if(board[i][j] != color) {	// 색상이 다르면 false
					return false;
				}
			}
		}
		return true;
	}
}

• Python

import sys
N = int(sys.stdin.readline())
board = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]

white = 0
blue = 0

def partition(x, y, n):
    global blue, white
    check = board[x][y]
    for i in range(x, x+n):
        for j in range(y, y+n):
            if check != board[i][j]:
                partition(x,y,n//2)#1사분면
                partition(x,y+n//2,n//2)#2사분면
                partition(x+n//2,y,n//2)#3사분면
                partition(x+n//2,y+n//2,n//2)#4사분면
                return
    if check==0:
        white+=1
        return
    else:  
        blue+=1
        return
            
partition(0,0,N)
print(white)
print(blue)