BOJ_2630 : 색종이 만들기

👉 문제링크

2630번: 색종이 만들기

---

---

🔸 문제 분석 🔸

• N x N 크기의 정사각형 종이를 같은 색으로만 이루어진 정사각형으로 자를 때 최소 개수를 출력한다.
  • 종이를 자르는 방법은 한 변의 길이를 절 반으로 하는 정사각형 4개를 만드는 것이다.
• 한 정사각형 범위가 모두 같은 색인지 체크하고, 같지 않다면 4등분으로 잘라 다시 색을 체크하는 재귀 메서드를 사용한다.
  • 재귀 메서드의 입력 값은 한 변의 길이와 좌상단의 좌표이다.

🔸 코드 🔸

import java.util.Scanner;

public class Main {
    private static int[][] arr;
    private static int white, blue;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        arr = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        cutting(n, 0, 0);
        System.out.println(white);
        System.out.println(blue);
    }

    private static int cutting(int n, int x, int y) {
//        print(n, x, y);
        int pick = arr[x][y];
        if (n > 1) {
            for (int i = x; i < x + n; i++) {
                for (int j = y; j < y + n; j++) {
                    if (arr[i][j] != pick) {
                        cutting(n / 2, x, y);
                        cutting(n / 2, x + n / 2, y);
                        cutting(n / 2, x, y + n / 2);
                        cutting(n / 2, x + n / 2, y + n / 2);
                        return 0;
                    }
                }
            }
        }
        if (pick == 0) white++;
        else blue++;
        return 0;
    }

    private static void print(int n, int x, int y) {
        System.out.println("\n==================(" + x +", "+ y +")========================");
        for (int i = x; i < x + n; i++) {
            for (int j = y; j < y + n; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }
}

🔸 코드 해석 🔸

• 하얀 색종이와 파란 색종이의 값을 클래스 멤버 변수로 두고 제귀 메서드 cutting()을 돌려 카운트한다.
  • 검사하는 범위의 색이 모두 같지 않다면 4등분으로 자르고, 같다면 그 색의 값을 카운트한다.
  • 4등분 할 때, n을 2등분하고, 그만큼 시작 좌표값을 움직여서 4번 cutting()에 입력해 재귀를 사용한다.

---

🔸 end 🔸

• 분할 정복 문제라는데 익숙치 않은 접근 방법이었지만, 많이 어렵지는 않았다.
• 재귀 메서드 사용이 생각보다 연습이 덜 된 것 같아서 재귀 문제를 풀어볼까 한다.
• 문제 접근, 풀이계획 메모를 작성했다.