Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

20. 분할 정복

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

Java / Python

3. 종이의 개수

1780번

쿼드트리와 비슷한데 4개 대신 9개로 나누는 문제

이번 문제는 N×N크기의 행렬로 표현되는 종이를 이용하는 문제입니다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있는데, 규칙에 따라 자르고 첫째 줄에 -1, 둘째 줄에 0, 셋째 줄에 1로만 채워진 종이의 개수를 출력하는 문제입니다. 이번에는 문제가 하나의 공간을 4개로 분할하는 것이 아닌 9개로 분할하여 풀어내는 문제입니다.

• Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {
 
	public static int[][] board;
	public static int ZERO = 0;	// 0
	public static int ONE = 0;	// 1
	public static int M_ONE = 0;	// -1
 
	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(M_ONE);	// -1
		System.out.println(ZERO);	// 0
		System.out.println(ONE);	// 1
 
	}
 
	
	public static void partition(int row, int col, int size) {
 
		// 같은 색상이면 해당 색상 카운트를 증가
		if (NumCheck(row, col, size)) {
			if(board[row][col] == -1) { 
				M_ONE++;
			}
			else if(board[row][col] == 0) {
				ZERO++;
			}
			else {
				ONE++;
			}
 
			return;
		}
 
		int newSize = size / 3;
		
		// 9칸으로 분할, 왼쪽 위 부터 오른쪽으로 1~9
		partition(row, col, newSize);								// 1
		partition(row, col + newSize, newSize);						// 2
		partition(row, col + 2 * newSize, newSize);					// 3
		
		partition(row + newSize, col, newSize);						// 4
		partition(row + newSize, col + newSize, newSize);			// 5
		partition(row + newSize, col + 2 * newSize, newSize);		// 6
		
		partition(row + 2 * newSize, col, newSize);					// 7
		partition(row + 2 * newSize, col + newSize, newSize);		// 8
		partition(row + 2 * newSize, col + 2 * newSize, newSize);	// 9
 
	}
 
	public static boolean NumCheck(int row, int col, int size) {
		int num = board[row][col];
 
		// 범위 내 number check
		for (int i = row; i < row + size; i++) {
			for (int j = col; j < col + size; j++) {
				if (num != board[i][j]) {
					return false;
				}
			}
		}
		return true;
	} 
}

• Python

N = int(input())
paper = [list(map(int, input().split())) for _ in range(N)]
m_one = 0
zero = 0
one = 0

def partition(x, y, n):
    global m_one, zero, one
    
    check = paper[x][y]
    for i in range(x, x + n):
        for j in range(y, y + n):
            if(paper[i][j] != check):
                for k in range(3):
                    for l in range(3):
                        partition(x + k * n//3, y + l * n//3, n//3)
                return
            
    if(check == -1):
        m_one += 1
    elif(check == 0):
        zero += 1
    else:
        one += 1
        
partition(0, 0, N)
print(f'{m_one}\n{zero}\n{one}')