문제 풀이 - 사다리 조작(JAVA)

사다리 조작

문제의 분할

우리가 해결해야 할 문제는 'i번 세로선의 결과는 i번이 나오도록 하기 위해 추가해야하는 가로선의 개수는 몇 개 인가?' 입니다. 이 문제는 '현재 사다리의 상태에서 $x$개의 가로선을 추가하면 i번 세로선의 결과는 i번이 나오는 사다리가 되는가?'를 풀 수 있으면 해결할 수 있습니다. boolean addRow(int rowCount) 함수를 만들면 됩니다. 사다리의 상태를 인자로 넘겨주는 것보다 전역 변수로 만드는 것이 더 메모리를 효율적으로 사용할 수 있기 때문에 추가할 가로선만 인자로 넘겨주면 됩니다.
addRow 함수를 호출하면 놓을 수 있는 모든 가로선의 위치에 가로선을 한 개 추가하고 추가할 가로선을 한 개 줄인 후 재귀 호출을 합니다.

기저 사례의 선택

1. 만약 추가할 가로선이 0개라면 i번 세로선의 결과가 i번이 나오는지 검사한 후 만족하면 성공 그렇지 않으면 실패합니다.

시간 복잡도 분석

addRow 함수를 한 번 호출할 때마다 가로선을 놓을 수 있는 모든 위치를 탐색합니다. 따라서 addRow 함수를 한 번 호출하면 $O(NH)$ 시간이 걸립니다. 놓을 수 있는 가로선의 개수 $x$가 1개 늘어날 때마다 탐색 횟수가 지수적으로 증가하므로 시간 복잡도는 $O((NH)^x)$입니다. 최대 $(10*30)^3=27,000,000$번 탐색하므로 충분히 시간 안에 풀 수 있습니다.

구현

import java.util.*;

public class Main {

    // 세로선의 개수
    public static int N;
    // 가로선의 개수
    public static int M;
    // 세로선마다 가로선을 놓을 수 있는 위치의 개수
    public static int H;
    // 사다리(H+1 * N+1 배열)
    // 세로선과 가로선의 위치가 1부터 시작하고 검사할 때 더 쉽게 하기 위해
    public static int[][] ladder;
    // 문제의 답
    public static int result;

    // 입력을 받는 함수입니다.
    public static void input() {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        M = scanner.nextInt();
        H = scanner.nextInt();

        ladder = new int[H + 1][N + 1];
        for (int i = 0; i < M; i++) {
            int row = scanner.nextInt();
            int column = scanner.nextInt();
            ladder[row][column] = 1;
        }
    }

    // 문제를 해결하는 함수입니다.
    public static void solve() {
        result = -1;
        for (int i = 0; i <= 3; i++) {
            if (addRow(i)) {
                result = i;
                break;
            }
        }
    }

    // 가로선의 개수를 rowCount개 추가하면 i번 세로선의 결과가 i번이 나오는 사다리를 만들 수 있는지 여부를 반환하는 함수입니다.
    public static boolean addRow(int rowCount) {
        if (rowCount == 0) {
            return isGoodLadder();
        }

        for (int i = 1; i <= H; i++) {
            for (int j = 1; j <= N - 1; j++) {
                if (canPlace(i, j)) {
                    ladder[i][j] = 1;
                    if (addRow(rowCount - 1)) return true;
                    ladder[i][j] = 0;
                }
            }
        }
        return false;
    }

    // i번 세로선의 결과가 i번이 나오는지 검사하는 함수입니다.
    public static boolean isGoodLadder() {
        for (int i = 1; i <= N; i++) {
            int currentColumn = i;
            for (int j = 1; j <= H; j++) {
                if (ladder[j][currentColumn] == 1) {
                    currentColumn++;
                }
                else if (ladder[j][currentColumn - 1] == 1) {
                    currentColumn--;
                }
            }
            if (i != currentColumn) return false;
        }
        return true;
    }

    // 주어진 위치에 가로선을 놓을 수 있는지 검사하는 함수입니다.
    public static boolean canPlace(int row, int column) {
        return ladder[row][column] == 0 && ladder[row][column - 1] == 0 && ladder[row][column + 1] == 0;
    }

    // 답을 출력하는 함수입니다.
    public static void output() {
        System.out.println(result);
    }

    public static void main(String[] args) {
        input();
        solve();
        output();
    }
}

회고

isGoodLadder 함수를 구현할 때 잔실수를 해서 시간이 오래 걸렸습니다. 좀더 집중력을 키워야할 것 같습니다.
위의 알고리즘은 중복된 사다리도 검사하기 때문에 그렇게 효율적이진 않습니다.