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

문제 링크

BOJ 2630번: 색종이 만들기

2630번: 색종이 만들기

 

풀이 과정

문제의 조건이 주어지고 만약 조건이 성립하지 않으면 분할하여 반복하는 구조 ⇒ 분할정복

 

시작점을 두고 시작점과 주어진 칸들의 값이 일치한다면 카운트, 아니라면 4분할 하는 방법으로 접근하였다

이 문제에서 핵심적인 부분은 divide함수 부분이다. 색종이의 길이를 n, 좌상단 시작점을 (y, x)로 변수명을 정하고 시작하였다.

 

만약 시작점과 종이의 칸의 숫자가 다르다면 분할을 해야하는데, 예를 들어 종이의 크기가 4인 경우이다

 

 

각 칸의 숫자가 일치하지 않아 종이가 4등분 된다면 전체 길이는 2로 감소하고, 분할된 종이의 우상단의 경우 시작점이 변경되어야 하는데 시작점은 종이의 절반만큼 증가했으므로 x가 2만큼 증가하게 된다.

 

위와 같은 방식으로 종이가 분할되는 경우는 총 4가지가 등장하게 된다.

divide(n / 2, y, x);
divide(n / 2, y + n / 2, x);
divide(n / 2, y, x + n / 2);
divide(n / 2, y + n / 2, x + n / 2);

만약 종이의 각 칸의 값들이 시작점과 일치한다면 cnt배열을 통해 시작점의 값을 index로 가진 값을 증가시켜주었다.

 

코드

import java.util.Scanner;

public class Main {
    static int[] cnt = new int[2];
    static int[][] paper;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        paper = new int[N][N];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                paper[i][j] = sc.nextInt();

        divide(N, 0, 0);
        for (int n : cnt)
            System.out.println(n);
    }

    static void divide(int n, int y, int x) {
        for (int i = y; i < y + n; i++) {
            for (int j = x; j < x + n; j++)
                if (paper[i][j] != paper[y][x]) {
                    divide(n / 2, y, x);
                    divide(n / 2, y + n / 2, x);
                    divide(n / 2, y, x + n / 2);
                    divide(n / 2, y + n / 2, x + n / 2);

                    return;
                }
        }

        cnt[paper[y][x]]++;
    }
}

 

제출 결과