사다리 조작

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

풀이

처음에 그냥 단순하게 백트래킹을 통해 모든 경우의 수를 다 탐색을 하게 되면 시간초과이다.

처음에 코드를 작성했을 때 예제는 통과되었지만 제출을 하면 시간초과를 만나 수정에 어려움을 겪었다.

문제를 풀 때 시간초과를 해결하는 방법은 우선 사다리를 추가하는 과정에서 정답이 나왔다면 이후는 볼 필요가 없다는 점이다. 그래서 만약 정답이 찾아졌다면 그 때 정답을 출력하고 멈춰준다.

또 나같은 경우 사다리 탐색과 정답인지 체크하는 메소드를 분리했는데 이를 하나로 통합하는 것이 시간단축에 더 유리했다.

그리고 사다리 표현에 있어서도 나같은 경우 사다리를 2로 표현하고 현재 위치에서 사다리가 있으면 이동하는 식으로 했는데 그럴 필요가 없이 더 간단하게 표현해서 조건식을 간소화해서 정답을 찾을 수도 있었다.

코드

import java.io.*;

public class Main {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int n, m, h;
    static int[][] ladder;
    static int answer = 4;
    static boolean finish = false;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);
        h = Integer.parseInt(input[2]);

        ladder = new int[h + 1][n + 1];

        for (int i = 0; i < m; i++) {
            String[] line = br.readLine().split(" ");
            int a = Integer.parseInt(line[0]);
            int b = Integer.parseInt(line[1]);
            ladder[a][b] = 1;
            ladder[a][b + 1] = 2;
        }
        if (runLadder()) {
            System.out.println(0);
        } else {
            for (int i = 1; i <= 3; i++) {
                answer = i;
                putLadder(0, i, 1, 1);
                if (finish)
                    break;
            }
            System.out.println((finish) ? answer : -1);
        }
        bw.flush();
        bw.close();
        br.close();
    }

    private static void putLadder(int cnt, int max, int x, int y) {
        if (finish)
            return;
        if (answer == cnt) {
            if (runLadder()) {
                finish = true;
            }
            return;
        }

        for (int j = y; j < n; j++) {
            int s = 1;
            if (j == y)
                s = x;
            for (int i = s; i <= h; i++) {
                if (ladder[i][j] == 0 && ladder[i][j + 1] == 0) {
                    ladder[i][j] = 1;
                    ladder[i][j + 1] = 2;
                    putLadder(cnt + 1, max, i + 1, j);
                    ladder[i][j] = 0;
                    ladder[i][j + 1] = 0;
                }
            }
        }
    }

    private static boolean runLadder() {
        for (int i = 1; i <= n; i++) {
            int start = i;
            int y = 1;
            for (int j = 0; j < h; j++) {
                if (ladder[y][start] == 1)
                    start++;
                else if (ladder[y][start] == 2)
                    start--;
                y++;
            }
            if (start != i)
                return false;
        }
        return true;
    }
}