[코드트리][백트래킹] 사다리 타기

코드 트리 링크 : https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-ladder-game/submissions?page=1&page_size=20

사다리 타기 제출 | 코드트리

 

문제 설명

사다리타기 게임은 세로줄 N개와 가로줄 M개로 구성된다.
각 가로줄은 특정 높이에서 인접한 두 세로줄을 연결한다.

예를 들어 가로줄 (a, b)가 주어졌다면, 이는 다음을 의미한다.

b번째 높이에서 a번 세로줄과 a+1번 세로줄이 연결된다.

 

사다리를 위에서 아래로 내려가면서 가로줄을 만나면 옆 세로줄로 이동한다.
문제는 여기서 한 단계 더 나아간다.

 

전체 가로줄을 모두 사용했을 때의 결과와 동일한 결과를 만들 수 있는 최소 가로줄 개수를 구해야 한다.

 

즉, 모든 가로줄이 꼭 필요한 것은 아닐 수 있다.
일부 가로줄만 선택해도 최종 결과가 같다면, 그중 최소 개수를 찾아야 한다.

 

접근 방법

처음에는 각 시작점에서 실제로 사다리를 타고 내려가는 방식으로 생각할 수 있다.

하지만 이 문제는 더 단순하게 볼 수 있다.

가로줄 하나는 결국 인접한 두 세로줄의 값을 교환하는 역할을 한다.

예를 들어 현재 상태가 다음과 같다고 하자.

1 2 3 4

 

여기서 2번 세로줄과 3번 세로줄을 연결하는 가로줄을 만나면 결과는 이렇게 된다.

1 3 2 4

 

즉, 가로줄 하나는 배열에서 인접한 두 값을 swap하는 것과 같다.

따라서 전체 사다리 결과는 다음 방식으로 구할 수 있다.

1. 세로줄 상태를 [1, 2, 3, ..., N]으로 초기화한다.
2. 가로줄을 높이 순서대로 정렬한다.
3. 각 가로줄을 만날 때마다 col과 col+1 위치를 swap한다.
4. 최종 배열이 사다리 결과가 된다.

 

 

1. 전체 가로줄을 사용한 목표 결과 만들기

먼저 모든 가로줄을 사용했을 때의 결과를 구한다.
이 결과를 target 배열에 저장한다.

static void makeTarget(){
    target = new int[N + 1];

    for(int i = 1; i <= N; i++){
        target[i] = i;
    }

    for(Line line : lines){
        int temp = target[line.col];
        target[line.col] = target[line.col + 1];
        target[line.col + 1] = temp;
    }
}

 

예를 들어 전체 가로줄을 사용했을 때 결과가 다음과 같다면:

3 4 1 2

 

이제 일부 가로줄만 선택해서도 이 결과를 만들 수 있는지 확인하면 된다.

---

2. 최소 개수를 찾는 방법

최소 개수를 찾아야 하므로, 가로줄을 다음 순서로 선택해본다.

0개 선택
1개 선택
2개 선택
3개 선택
...
M개 선택

 

이렇게 탐색하면 처음으로 target과 같은 결과가 나오는 순간, 그 개수가 최소값이다.

for(int limit = 0; limit <= M; limit++){
    current = new int[N + 1];

    for(int i = 1; i <= N; i++){
        current[i] = i;
    }

    if(dfs(0, 0, limit)){
        System.out.println(limit);
        return;
    }
}

 

여기서 limit은 현재 선택할 가로줄 개수다.

예를 들어 limit = 3이면, 전체 가로줄 중 3개를 골라서 목표 결과를 만들 수 있는지 확인한다.

 

3. DFS로 조합 탐색하기

DFS에서는 가로줄을 하나씩 선택한다.
선택한 가로줄은 현재 배열에 바로 swap으로 반영한다.

static boolean dfs(int index, int count, int limit){
    if(count == limit){
        return Arrays.equals(current, target);
    }

    if(index == M){
        return false;
    }

    if(count + (M - index) < limit){
        return false;
    }

    for(int i = index; i < M; i++){
        int col = lines[i].col;

        swap(col, col + 1);

        if(dfs(i + 1, count + 1, limit)){
            return true;
        }

        swap(col, col + 1);
    }

    return false;
}

 

여기서 중요한 부분은 선택 후 복구다.

swap(col, col + 1);

 

가로줄을 선택했으므로 현재 상태에 반영한다.

이후 재귀 탐색이 끝나면 다시 같은 위치를 swap한다.

swap(col, col + 1);

 

swap은 두 번 하면 원래 상태로 돌아온다.
그래서 별도의 배열 복사 없이 DFS를 진행할 수 있다.

---

4. 가지치기

이 조건은 불필요한 탐색을 줄이기 위한 가지치기다.

if(count + (M - index) < limit){
    return false;
}

 

의미는 이렇다.

현재까지 count개를 선택했다. 앞으로 선택할 수 있는 가로줄은 M - index개 남았다. 그런데 이 둘을 다 더해도 limit개를 채울 수 없다면 더 볼 필요가 없다.

 

예를 들어 limit = 5인데, 현재까지 2개를 선택했고 남은 가로줄이 2개뿐이라면 최대 4개밖에 선택할 수 없다.

count = 2
남은 가로줄 = 2
최대 선택 가능 개수 = 4
limit = 5

→ 불가능

 

따라서 바로 탐색을 중단한다.

 

전체 코드

정렬: O(M log M)
target 생성: O(N + M)
DFS 조합 탐색: O((N + M) * 2^M)

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;
    static Line[] lines;
    static int[] target;
    static int[] current;

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        lines = new Line[M];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int col = Integer.parseInt(st.nextToken());
            int row = Integer.parseInt(st.nextToken());

            lines[i] = new Line(col, row);
        }

        Arrays.sort(lines, (a, b) -> a.row - b.row);

        makeTarget();

        for(int limit = 0; limit <= M; limit++){
            current = new int[N + 1];

            for(int i = 1; i <= N; i++){
                current[i] = i;
            }

            if(dfs(0, 0, limit)){
                System.out.println(limit);
                return;
            }
        }
    }

    static boolean dfs(int index, int count, int limit){
        if(count == limit){
            return Arrays.equals(current, target);
        }

        if(index == M){
            return false;
        }

        if(count + (M - index) < limit){
            return false;
        }

        for(int i = index; i < M; i++){
            int col = lines[i].col;

            swap(col, col + 1);

            if(dfs(i + 1, count + 1, limit)){
                return true;
            }

            swap(col, col + 1);
        }

        return false;
    }

    static void makeTarget(){
        target = new int[N + 1];

        for(int i = 1; i <= N; i++){
            target[i] = i;
        }

        for(Line line : lines){
            int temp = target[line.col];
            target[line.col] = target[line.col + 1];
            target[line.col + 1] = temp;
        }
    }

    private static void swap(int a, int b){
        int temp = current[a];
        current[a] = current[b];
        current[b] = temp;
    }

    static class Line{
        int col;
        int row;

        Line(int col, int row){
            this.col = col;
            this.row = row;
        }
    }
}