[자바/백트래킹] 코드트리. 사다리 타기

문제 보기

🤔 Intuition

사다리타기는 마치 시뮬레이션처럼 생각하여 2차원 배열로 구현할 수 있을 것으로 봤고, 가능한 경우를 구할 때에는 이미 있는 라인에서 최대한 지워보는 방식으로 구현하면 될 것으로 봤다. 결국 사다리타기 결과가 동일하기 위해선 반드시 기존 경우의 수의 부분집합으로 구성되어야 하기 때문이다.

부분집합을 구현하는 방법은 백트래킹으로 찾아주면 된다.

🔎 Algorithm & Complexity

• @algorithm backtracking (powerset)
• @time O(2^M) ; 142 ms
• @memory O(N*M) ; 12 MB

👨🏻‍💻 Logic

1. 주어진 사다리 정보를 이용하여 기존 결과를 뽑아낸다. (시뮬레이션 활용)
2. 전체 경우의 부분집합을 구해보며, 가장 많이 제거한 경우를 답으로 출력한다.

public class CodeTree_사다리타기 {
    private static int N, M;
    private static int[][] ladder;
    private static int[] res;
    private static int ans;
    private static List<int[]> lines = new ArrayList<>();

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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 세로줄 수
        M = Integer.parseInt(st.nextToken()); // 가로줄 수
        ladder = new int[16][N + 1];
        ans = M;

        int a, b;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            lines.add(new int[]{a, b});
            ladder[b][a] = 1; // b번째 세로의 a번 라인에서 a+1로 가는 걸 나타냄
            ladder[b][a + 1] = -1; // b번째 세로의 a+1번 라인에서 a로 가는 걸 나타냄
        }

        res = newRes();

        go(0, 0);
        System.out.println(ans);
    }

    private static int[] newRes() {
        int[] res = new int[N + 1];
        int col, row;
        for (int i = 1; i <= N; i++) {
            col = i;
            row = 15;
            while (row > 0) {
                if (ladder[row][col] != 0) {
                    col += ladder[row][col];
                }
                row--;
            }
            res[i] = col;
        }
        return res;
    }

    private static void go(int depth, int cnt) {
        if (depth == M) {
            int[] tmp = newRes();
            if (sameResWith(tmp)) {
                ans = Math.min(ans, M - cnt);
            }
            return;
        }

        int[] line = lines.get(depth);
        int a = line[0];
        int b = line[1];
        ladder[b][a] = 0;
        ladder[b][a + 1] = 0;
        go(depth + 1, cnt+1);
        ladder[b][a] = 1;
        ladder[b][a + 1] = -1;
        go(depth + 1, cnt);

    }

    private static boolean sameResWith(int[] tmp) {
        for (int i = 1; i <= (N / 2) + 1; i++) {
            if (tmp[i] != res[i] || tmp[N - i + 1] != res[N - i + 1]) {
                return false;
            }
        }
        return true;
    }
}