[백준] 2603번 - 색종이 만들기 JAVA 풀이

2603 - 색종이 만들기 

문제

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

2630번: 색종이 만들기

문제 요약:

입력으로 주어진 종이의 한 변의 길이 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

 

문제 정의

색종이를 쪼갤 수 있을 때 까지 쪼개는데, 도중에 쪼개진 색종이의 모든 영역이 같은 색이면 쪼개는 것을 그만하고 색깔에 맞는 변수의 값을 증가시킨다.

 

색종이를 쪼개는 것은 반복된 행위이기 때문에 재귀로 해소가 가능하다. 

쪼개진 영역은 다음과 같다.

 

N/2를 정하는 방법은 다음과 같다.

1. 0~7의 mid = 4

2. 0~4의 mid = 2

    4~8의 mid = 6

3. 0~2의 mid = 1

    2~4의 mid = 3

    4~6의 mid = 5

    6~8의 mid = 7

-> mid = (start + end ) / 2

 

해당 아이디어를 이용해서 재귀로 이 문제를 풀이할 수 있다.

이 문제에서는 기저 조건이 2개가 있다.

1. start 좌표와 end 좌표의 차이가 1이면 최소 cell 이다. 즉, 더이상 쪼갤 수 없다.

최소 cell인 경우, 해당 영역의 색상을 확인하고, 색상 변수의 값을 증가시킨다.

return 이 일어난다.

 

2. 두번째 기저조건(종료시점)은 영역의 모든 셀이 같은 색상으로 구성된 경우이다. 

이러한 영역은 더이상 탐색할 필요가 없으니 return한다.

 

종료조건에 걸리지 못한단면, (start , N/2) 만큼 색종이를 더 쪼개야 한다.

하나의 색종이를 쪼개는 경우의 수는 총 4개이다.

- 모든 셀이 같은 색상인 색종이는 완성됐으므로 더이상 재귀 하지 않는다.

- 그렇지 않은 경우는 최소 cell일 때 까지 계속 쪼갠다.

 

정리

1. 기저조건에 걸리는지 확인하고 

2. 기저조건에 걸린다면 해당하는 색상을 증가시킨 후 return 한다.

2-1. 기저조건에 걸리지 않는다면 더 쪼개기 위해 범위를 재설정한 후 재귀 호출한다.

 

전체 코드

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

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        countColorPapers(0, N, 0, N); // dfs 실행
        System.out.println(white);
        System.out.println(blue);
    }

    static void countColorPapers(int sx, int ex, int sy, int ey) {
        if (isUniformColor(sx, ex, sy, ey)) { // 색종이를 구성하는 모든 셀이 같은 색인지 확인
            if (map[sy][sx] == 1) { // 해당 cell이 blue인지 white인지 확인
                blue++;
            } else {
                white++;
            }
            return;
        }

        // white와 blue가 색종이에 섞여있는 경우 색종이의 크기를 조정한다.
        // 색종이가 나누어질 수 있는 경우는 총 4가지이다. (제1사분면, 제2사분면, 제3사분면, 제4사분면)
        int xMid = (sx + ex) / 2;
        int yMid = (sy + ey) / 2;
        countColorPapers(sx, xMid, sy, yMid); // 제2사분면
        countColorPapers(xMid, ex, sy, yMid); // 제1사분면
        countColorPapers(sx, xMid, yMid, ey); // 제3사분면
        countColorPapers(xMid, ex, yMid, ey); // 제4사분면
    }

    static boolean isUniformColor(int sx, int ex, int sy, int ey) {
        int color = map[sy][sx];
        for (int i = sy; i < ey; i++) {
            for (int j = sx; j < ex; j++) {
                if (map[i][j] != color) return false;
            }
        }
        return true;
    }
}