[JAVA] 백준 (실버2) 2630번 색종이 만들기

링크

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

---

문제 설명

정답률 69.670%

아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

---

입력 예제

8
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 1 1 1 1
0 1 0 0 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1

---

출력 예제

9
7

---

풀이

이 문제는 분할 정복으로 풀 수 있다. 분할 정복 알고리즘은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다.

색종이가 한가지 색이 아닐 경우 4등분을 한다. 그리고 각 종이에 대해 다시 한가지 색만 있는지 판단을 한 뒤 아닐 경우 4등분을 하고 한가지 색만 남을 때까지 이를 반복한다.

색종이가 한가지 색인지 판단하는 메서드는 다음과 같다. 색종이의 길이와 좌측 상단 좌표를 인자로 넘겨 해당 색종이의 모든 좌표를 탐색한다.

private static boolean hasOneColor(int length, int r, int c) {
    int color = paper[r][c];
    for (int i = r; i < r + length; i++) {
        for (int j = c; j < c + length; j++) {
            if (paper[r][j] != color) {
                return false;
            }
        }
    }
    return true;
}

색종이를 4등분 하는 메서드는 재귀로 구성한다. 각 색종이의 좌측 상단 좌표를 현재 색종이의 길이의 절반으로 갱신하여 다음과 같이 재귀를 호출한다.

private static void recur(int length, int r, int c) {
    length /= 2;
    recur(length, r, c);  //1번 종이
    recur(length, r, c + length);  //2번 종이
    recur(length, r + length, c);  //3번 종이
    recur(length, r + length, c + length);  //4번 종이
}

전체 코드

//백준
public class Main {

    static int[][] paper;
    static int white;
    static int blue;

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //입력값 초기화
        int N = Integer.parseInt(br.readLine());
        paper = new int[N][N];
        for (int i = 0; i < N; i++) {
            paper[i] = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();
        }

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

    private static void recur(int length, int r, int c) {
    	//한가지 색일 경우 재귀 종료
        if (hasOneColor(length, r, c)) {
            if (paper[r][c] == 0) {
                white++;
            } else {
                blue++;
            }
            return;
        }

        length /= 2;
        recur(length, r, c);  //1번 종이
        recur(length, r, c + length);  //2번 종이
        recur(length, r + length, c);  //3번 종이
        recur(length, r + length, c + length);  //4번 종이
    }

    private static boolean hasOneColor(int length, int r, int c) {
        int color = paper[r][c];
        for (int i = r; i < r + length; i++) {
            for (int j = c; j < c + length; j++) {
                if (paper[i][j] != color) {
                    return false;
                }
            }
        }
        return true;
    }
}