[알고리즘] 백준 2339 - 석판 자르기

문제본문

문제 난이도를 제공해주는 것은 나에게 오히려 독이 되는 것 같다. 이 문제는 골드 1 문제로 시작부터.. 내가 풀 수 있을까? 하던 문제 그래서 조금 고민하다 힌트를 우선 보았었다 ㅜㅜ

 

재귀호출이 자주 쓰이는 분할정복 문제인 것을 알기 때문에 함수부터 작성했다. 2차원 배열인 board에서 불순물이 하나도 없고 결정이 오직 1개 존재하도록 매 재귀호출 마다 board를 탐색해야 한다. 그런데 문제는 쿼드 트리처럼 정사각형으로 잘리는 것이 아닌 불순물의 위치에 따라 잘리기 때문에 분할된 문제의 크기를 정수로 나타내기 어려워서 가로와 높이 모두 시작과 끝을 매개변수로 넘겨주었다.

public int division(int startX, int endX, int startY, int endY, int[][] board...(생략)) {

  for (int y = startY; y < startY; y++) {
   for (int x = startX; x < endX; x++) { 
    }
  }
}

 

 

분할정복과 재귀함수의 구현하기에 가장 쉽게 접근하는 방법은 더이상 분할(or 재귀)되지 않고 함수가 종료되는 상황을 구하는 것 같다. 이 문제에서는 탐색하는 범위에서 결정체가 오직 1개, 불순물이 없어야 한다라는 것이 조건이다. 따라서 위의 탐색 범위에서 해당 개체의 숫자를 구하고 비교해서 쉽게 구했다!

public int division(int startX, int endX, int startY, int endY, int[][] board...(생략)) {
        int starCount = 0;
        int impuritiesCount = 0;

        for (int x = startX; x < endX; x++) {
            for (int y = startY; y < endY; y++) {
                if (board[y][x] == 2) {
                    starCount++;
                } else if (board[y][x] == 1) {
                    impuritiesCount++;
                }
            }
        }
        //결정체는 1개는 꼭 있어야한다. 따라서 1개 이상있어도 틀린 경우
        if (starCount == 0) return 0;
        else if (starCount == 1 && impuritiesCount == 0) return 1;

 

그럼 이제 남은 구현은 탐색 범위에 불순물이 포함되어 있는 경우이다. 이 문제는 나눠지는 경우의 수를 구하는 거기 때문에 불순물에 대해 가로 or 세로로 나누어 가능한 경우의 수를 구해야 한다. 그런데 불순물에 대한 위치 정보를 다시 탐색해가면서 찾는 것보다 처음 탐색할 때 불순물의 위치 정보를 저장하는 것이 더 효율적이라 생각했다.

public int division(int startX, int endX, int startY, int endY, int[][] board...(생략)) {
        int starCount = 0;
        int impuritiesCount = 0;

        //불순물 위치 정보 저장
        int[][] impuritiesPosition = new int[(endX - startX) * (endY - startY)][2];

        for (int x = startX; x < endX; x++) {
            for (int y = startY; y < endY; y++) {
                if (board[y][x] == 2) {
                    starCount++;
                } else if (board[y][x] == 1) {
                    //불순물 위치 정보 저장
                    impuritiesPosition[impuritiesCount][0] = y;
                    impuritiesPosition[impuritiesCount][0] = x;
                    impuritiesCount++;
                }
            }
        }
        //결정체는 1개는 꼭 있어야한다. 따라서 1개 이상있어도 틀린 경우
        if (starCount == 0) return 0;
        else if (starCount == 1 && impuritiesCount == 0) return 1;

그런데 백준 사이트에서 채점을 해보니 메모리 초과가 발생했다. 생각해보니 불순물의 위치가 변경되는 것도 아니고 분할할 때마다 같은 정보를 계속 저장한다는 것이 이상하기도 했다. 또 문제에서 N의 범위가 1 <= N <= 20이기 때문에 또 한번 탐색한다고 해도 크게 문제가 없어보여서 다시 한번 불순물의 위치를 반복문으로 탐색하는 것으로 변경했다.

        (생략)
       int answer = 0;

        for (int x = startX; x < endX; x++) {
            for (int y = startY; y < endY; y++) {
              if (board[y][x] == 1) {
                  //불순물일 경우
                }
            }
        }

불순물일 경우, 문제에서는 해당 위치에서 가로 또는 세로로 석판을 자른다고 나와있다. 그리고 이전에 자른 방향으로는 동일하게 자를 수 없다. 그말은 가로로 잘라 분할된 석판을 또 가로로 자를 수 없다는 말. 하지만 처음 석판을 자를 때는 가로 또는 세로 둘다 가능하다.
다행이도 간단히 규칙성이 보였다. 가로로 잘랐다면 다음 분할된 재귀 함수에서는 무조건 세로로 자르면 된다. 해당 값을 의미하는 변수를 함수 매개변수에 추가하였다.

 /**
     *
     * @param direction 0 : 가로, 1 : 세로  처음에는 -1을 주어 둘다 탐색하게 만든다.
     * @return
     */
    public static int division(int startX, int endX, int startY, int endY, int[][] board, int direction) {

                //불순물 일경우
                  if (direction != 0) { //세로로 자르기 가능

                  }
                  if (direction != 1) { //가로로 자르기 가능

                  }
    }

그럼 이제 정말 남은 구현은 경우의 수를 구하는 것이다! 이 부분은 힌트덕분에 쉽게 알게 되었다.
경우의 수 성질에 의해 석판을 반으로 나눠서 왼쪽에서 2개의 경우의 수가 생기고 오른쪽에서 3개의 경우의 수가 생기면 총 경우의 수는 A * B = 6이라고 한다.

A = {a1, a2}, B = {b1, b2, b3} result = {a1b1, a1b2, a1b3, a2b1, a2b2, a2b3}

따라서 곱셈으로 표현해야 한다.

                  if (direction != 0) { //세로로 자르기 가능
                      answer += division(startX, x, startY, endY, board, 0) *
                              division(x + 1, endX, startY, endY, board, 0);
                  }
                  if (direction != 1) { //가로로 자르기 가능
                      answer += division(startX, endX, startY, y, board, 1) *
                              division(startX, endX, y + 1, endY, board, 1);
                  }

 

총 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] board = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = scanner.nextInt();
            }
        }
        int answer = division(0, n, 0, n, board, -1);
        System.out.println(answer == 0 ? -1 : answer);
    }

    /**
     *
     * @param direction 0 : 가로, 1 : 세로
     * @return
     */
    public static int division(int startX, int endX, int startY, int endY, int[][] board, int direction) {
        int starCount = 0;
        int impuritiesCount = 0;

        for (int x = startX; x < endX; x++) {
            for (int y = startY; y < endY; y++) {
                if (board[y][x] == 2) {
                    starCount++;
                } else if (board[y][x] == 1) {
                    impuritiesCount++;
                }
            }
        }
        if (starCount == 0) return 0;
        else if (starCount == 1 && impuritiesCount == 0) return 1;

        int answer = 0;

        for (int x = startX; x < endX; x++) {
            for (int y = startY; y < endY; y++) {
              if (board[y][x] == 1) {
                  if (direction != 0) { //세로로 자르기 가능
                      answer += division(startX, x, startY, endY, board, 0) *
                              division(x + 1, endX, startY, endY, board, 0);
                  }
                  if (direction != 1) { //가로로 자르기 가능
                      answer += division(startX, endX, startY, y, board, 1) *
                              division(startX, endX, y + 1, endY, board, 1);
                  }
                }
            }
        }

        return answer;
    }
}

참고

• 분할정복