[백준 1780] 종이의 개수 - Java 코드 (분할정복)

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

1780번: 종이의 개수

 

문제

 

이해

분할정복은 매트릭스가 주어지며,

잘라야하는 숫자의 k승 이하로 주어진다.

해당 문제는 3의 k승 이하로 주어졌으며, 3으로 분할정복할때 나누어 떨어지는 input임을 알 수 있다.

 

 

 

풀이

입력은 BufferedReader로

결과는 HashMap에 -1, 0 , 1을 각각 저장해주는 형태로 구현하였다.

물론 3칸짜리 배열을 이용해도 괜찮다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

// 319,864 kb , 1036 ms
public class Main {
    static int[][] arr; // input matrix
    static HashMap<Integer, Integer> map = new HashMap<>(); // output map
    static int flag;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        for (int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine()," ");
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        br.close();
        // init map
        map.put(-1,0);
        map.put(0,0);
        map.put(1,0);
        // 분할정복
        divide(0,0,n);
        // 출력
        System.out.println(map.get(-1));
        System.out.println(map.get(0));
        System.out.println(map.get(1));

    }
    static void divide(int row,int col,int size){
        flag = arr[row][col];
        if(checkNum(row,col,size)){
            map.put(flag,map.get(flag)+1);
            return;
        }
        int newSize = size/3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                divide(row+(newSize*i),col+(newSize*j),size/3);
            }
        }
    }
    static boolean checkNum(int row, int col, int size){
        for (int i = row; i < row + size; i++) {
            for (int j = col; j < col + size; j++) {
                if (flag != arr[i][j]) {
                    return false;
                }
            }
        }
        return true;

    }
}

분할과 정복을 위한 divide, checkNum 함수에 대해서 이야기를 좀 더 해보자면,

 

1) checkNum : 정복 메소드

checkNum 은 탐색해야하는 분할된 크기의 매트릭스 안에서 모든 값이 같은지를 체크해주는 함수이다.

값이 모두같아 분할할 필요가 없다면, true를 반환하면서 해당 값을 저장하고 함수를 종료시키도록 만들어주었다.

 

2) divide: 분할 메서드

divide는 9조각으로 분할하여 재귀적으로 호출되도록 구현된 부분이다.

이중 for문 (3X3) 은 언제나 9번 돌며,

기존 Size를 3으로 나누어 새로운 9조각의 매트릭스의 시작점과 탐색범위를 divide에 넘겨

분할정복을 구현해주었다. 

 

divide(row,col,newSize);
divide(row,col+newSize,newSize);
divide(row,col+(newSize*2),newSize);

divide(row+newSize,col,newSize);
divide(row+newSize,col+newSize,newSize);
divide(row+newSize,col+(newSize*2),newSize);

divide(row+(2*newSize),col,newSize);
divide(row+(2*newSize),col+newSize,newSize);
divide(row+(2*newSize),col+(newSize*2),newSize);

 

위와같이 단순히 9번의 호출문을 적어주는것보다

반복문 구조를 활용한 재귀호출이 훨씬 낫다.

 

어떠한 분할정복에서도 활용되는 뼈대이므로 기억하자.