[백준] 2630번_색종이 만들기(Java)

문제 풀이

백준의 2630번 문제입니다. 문제 출처

(1) 문제 파악

(2) 문제 풀이 방법 생각하기

이 문제는 분할 정복을 사용해서 풀 수 있습니다. (큰 문제가 작은 문제로 쪼개지기 때문에 가능합니다!)

특정 사각형 범위가 모두 같은 색상인지를 확인하고, 다른 색이 섞여있다면 절반 사이즈의 사각형 4곳을 동일한 방식으로 조사하면 되는 것이죠!

(3) 시간 복잡도 확인

시간 제한은 1초 입니다. 즉, 대략 1억번 연산 안에 문제를 해결해야 합니다.

\[2 <= N <= 128\]

• 재귀 함수를 통해 사각형을 자르는 연산: O(logN)
• 사각형 범위가 모두 같은 색상인지 확인하는 연산: O(N^2)

종합적으로 보았을 때 해당 풀이의 시간 복잡도는 O(logN * N^2) 이므로 1초 내에 문제 해결이 가능합니다.

(4) 구현

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static int[][] paper;
    static int blue = 0;
    static int white = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        paper = 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++) {
                paper[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        solution(0, 0, N);
        
        System.out.println(white);
        System.out.println(blue);

        br.close();
    }

    static void solution(int x, int y, int size) {
        int result = sameColor(x, y, size);

        if(result == 1) {
            blue++;
            return;
        } else if(result == 0) {
            white++;
            return;
        }

        solution(x, y, size/2);
        solution(x+(size/2), y, size/2);
        solution(x, y+(size/2), size/2);
        solution(x+(size/2), y+(size/2), size/2);
    }

    /***
     * 
     * @param startX 왼쪽 최상단 x좌표
     * @param startY 왼쪽 최상단 y좌표
     * @param size 사각형 사이즈
     * @return 모두 같은 색상이면 color 반환, 다르면 -1 반환
     */
    static int sameColor(int startX, int startY, int size) {
        int color = paper[startX][startY];

        for(int i=startX; i<startX+size; i++) {
            for(int j=startY; j<startY+size; j++) {
                if(paper[i][j] != color) {
                    return -1;
                }
            }
        }
        return color;
    }
}