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

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

 

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

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

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

---

1.  아이디어

 

현재 바라보는 색종이의 영역을 4등분하는 재귀 함수와 현재 영역이 같은 색으로 이루어져 있는지 판단하는 메서드의 조합으로 해결했다.

---

2. 문제풀이

 

재귀 함수는 현재 바라보는 색종이의 왼쪽 위와 오른쪽 아래 좌표(영역 바깥)를 파라미터로 받는다. 이후 해당 영역이 같은 색으로 이루어져 있는지 hasManyColor라는 boolean을 반환하는 메서드로 확인한 후 여러 색으로 이루어져 있으면 색종이를 4등분해서 재귀를 다시 도는 방식으로 구현했다.

---

3. 코드

 

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

public class Main {

    private static final int WHITE = 0;
    private static final int BLUE = 1;
    private static int whiteCnt = 0;
    private static int blueCnt = 0;

    private static int[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

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

        recur(0, 0, N, N);

        System.out.println(whiteCnt);
        System.out.println(blueCnt);
    }

    private static void recur(int r1, int c1, int r2, int c2) {
        if (hasManyColor(r1, c1, r2, c2)) {
            int midR = (r1 + r2) / 2;
            int midC = (c1 + c2) / 2;

            recur(r1, c1, midR, midC);
            recur(r1, midC, midR, c2);
            recur(midR, c1, r2, midC);
            recur(midR, midC, r2, c2);
        }
    }

    private static boolean hasManyColor(int r1, int c1, int r2, int c2) {
        int color = map[r1][c1];

        for (int r = r1; r < r2; r++) {
            for (int c = c1; c < c2; c++) {
                if (map[r][c] != color) return true;
            }
        }

        if (color == WHITE) whiteCnt++;
        else if (color == BLUE) blueCnt++;

        return false;
    }

}

---

4. 후기