[Java] 백준 2630번 : 색종이 만들기

문제

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

2630번: 색종이 만들기

 

 

풀이 과정

전체에서 계속 4등분으로 자르다보면 크기가 1인 사각형까지 도달하게 된다. 크기가 1인 사각형은 자신이 흰색인지, 파란색인지 정보를 반환한다.

이를 호출한 곳에서 크기가 1인 사각형 4개의 결과를 확인하고, 모두 0이거나 1이면 그 숫자 그대로 반환하고 하나라도 일치하지 않으면 색종이 개수에 더하고 2를 반환하도록 했다. 

 

이 방법 말고도 자르기 전에, 이중반복문으로 해당 크기의 색종이에 있는 수가 모두 일치한지 확인하고 하나라도 다르면 자르도록 하는 방법이 있다. 이 방법은 큰 색종이일 경우, 자르는 횟수가 적어 빠르지만, 확인한 장소를 또 확인해서 비효율적인 측면이 있어서 재귀로 풀었다. 

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

public class Main {

    static int[] result;
    static int[][] map;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        result = new int[3];
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++){
                map[i][j] = st.nextToken().charAt(0) - '0';
            }
        }

        result[findSqaure(0, 0, N)]++;

        StringBuilder sb = new StringBuilder();
        sb.append(result[0]).append("\n").append(result[1]);
        System.out.println(sb);
    }

    public static int findSqaure(int x, int y, int size){
        if(size == 1){
            return map[x][y];
        }

        int[] temp = new int[3];
        size/=2;
        temp[findSqaure(x, y, size)]++;
        temp[findSqaure(x, y+size, size)]++;
        temp[findSqaure(x+size, y, size)]++;
        temp[findSqaure(x+size, y+size, size)]++;

        if(temp[0] == 4){
            return 0;
        }
        else if(temp[1] == 4){
            return 1;
        }
        else{
            result[0] += temp[0];
            result[1] += temp[1];
            return 2;
        }
    }
}

 

 

결과