[백준 2630] 색종이 만들기 (JAVA)

백준 2630번 문제 - 색종이 만들기

2630번: 색종이 만들기

---

문제 분석

•  

 

• 2차원 배열로 흰색 확은 파란색으로 색이 칠해진 종이가 주어진다. (NxN)
• 종이를 모두 같은 색으로 칠해져 있을 때까지 정사각형으로 자른다.
  (혹은 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.)
• • N -> N/2 -> N/2/2 -> ... -> 1
• 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성해라 

---

해결 포인트

 

• 1번째 방법 : 앞, 위 색을 확인하고 다 자신과 다른 색이면 해당 색종이 개수 증가
  • 정사각형으로 자르는 방식이 존재한다는 것을 까먹음 (직사각형일 경우 가능할 듯)
• 2번째 방법 : 구간합 ?, 구간합을 구해서 구간 합이 0이거나 색종이 개수와 동일할 경우 해당 색종이 개수 증가
  • 어떻게 확인하지?...? 어려워
• 3번째 방법 : 합병 정렬 사용 (성공)
  • [0,0] ~ [N,N] : 모두 동일한지 확인 (확인하는 사이즈 N)
  • 동일할 경우, 해당 색종이 개수 증가
  • 동일하지 않을 경우, 4등분 (확인하는 사이즈 N/2)
    1. [0,0] ~ [N/2,N/2] : 모두 동일한지 확인
    2. [N/2,0] ~ [N,N/2] : 모두 동일한지 확인
    3. [0,N/2] ~ [N/2,N] : 모두 동일한지 확인
    4. [N/2,N/2] ~ [N,N] : 모두 동일한지 확인

 

---

코드

 

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

public class Main {
    public static int N;
    public static int [] counts;
    public static int [][] papers;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        counts = new int[2];
        N = Integer.parseInt(br.readLine());

        papers = new int[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                papers[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        marge(0,0, N);

        bw.write(counts[0] + "\n" + counts[1]);

        bw.flush();
        bw.close();
    }

    public static void marge(int x, int y, int size) {
        if(size <= 0) return;

        int start = papers[x][y];
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if(papers[x+i][y+j] != start) {
                    marge(x,y,size/2);
                    marge(x,y + size/2, size/2);
                    marge(x + size/2, y, size/2);
                    marge(x + size/2,y + size/2, size/2);
                    return;
                }
            }
        }

        counts[start]++;
    }

    public static boolean isCheckRound(int i, int j) {
        return (i >=0 && j >= 0 && i < N && j < N);
    }
}