P.2098 외판원 순회

코드

1. Top-down

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.stream.Stream;

public class Main {

    static int n;
    static int[][] matrix;
    static int[][] dp;

    static int MAX;
    static final int INF = 16_000_001;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        matrix = new int[n][n];
        for (int i = 0; i < n; i++) matrix[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        MAX = (1 << n) - 1;
        dp = new int[n][(int)Math.pow(2, n)];
        for (int i = 0; i < n; i++) Arrays.fill(dp[i], -1);

        bw.write(Integer.toString(dfs(0, 1)));
        bw.flush();
    }

    private static int dfs(int curCity, int curBit) {
        if (curBit == MAX) {
            if (matrix[curCity][0] != 0) return matrix[curCity][0];
            else return INF;
        }

        if (dp[curCity][curBit] != -1) return dp[curCity][curBit];
        dp[curCity][curBit] = INF;

        for (int i = 0; i < n; i++) {
            if ((curBit & (1 << i)) == 0 && matrix[curCity][i] != 0) {
                dp[curCity][curBit] = Math.min(dp[curCity][curBit], matrix[curCity][i] + dfs(i, (curBit | 1 << i)));
            }
        }

        return dp[curCity][curBit];
    }
}

2. Bottom-up

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

public class Main {

    static int n;
    static int[][] matrix;
    static int[][] dp;

    static int MAX;
    static final int INF = 16_000_001;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        matrix = new int[n][n];
        for (int i = 0; i < n; i++) matrix[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        MAX = (1 << n) - 1;
        dp = new int[n][(int)Math.pow(2, n)];
        for (int i = 0; i < n; i++) Arrays.fill(dp[i], INF);
        dp[0][1] = 0;

        bw.write(Integer.toString(solve()));
        bw.flush();
    }

    private static int solve() {
        for (int bit = 0; bit < (1 << n); bit++) {
            for (int cur = 0; cur < n; cur++) {
                if ((bit & (1 << cur)) == 0) continue;
                for (int prev = 0; prev < n; prev++) {
                    if ((bit & (1 << prev)) != 0 && cur != prev && matrix[prev][cur] != 0) {
                        dp[cur][bit] = Math.min(dp[cur][bit], dp[prev][bit ^ (1 << cur)] + matrix[prev][cur]);
                    }
                }
            }
        }

        int result = INF;
        for (int i = 1; i <n; i++) {
            if (matrix[i][0] != 0)
                result = Math.min(result, dp[i][MAX] + matrix[i][0]);
        }

        return result;
    }
}

코드 설명

외판원이 방문한 도시를 저장하기 위해 비트마스킹을 이용했다.

처음에는 BottomUp방식으로 아이디어를 생각했는데 인터넷을 참조하다보니 TopDown을 먼저 접하게 됐고 그 이후에 BottomUp으로 다시 풀어보았다.

 

1. Bottom-Up

dp[n][bit] = 출발지점부터 bit에 저장된 도시들을 거친 후 n번째 도시까지 도달했을 때 최소 비용

먼저 현재 비트(bit)와 현재 도시(n)을 정한다.

이 상태에서 이전 도시를 정한다.

for (int bit = 0; bit < (1 << n); bit++) {
    for (int cur = 0; cur < n; cur++) {
        for (int prev = 0; prev < n; prev++) {
        }
    }
}

이전 도시를 고를 수 있는 조건은 다음과 같다.

1. 이전에 이 도시를 방문한 흔적이 있어야 한다.
2. 이 도시에서 현재 도시로 갈 수 있는 길이 있다.

1번을 체크하기 위해서 비트를 확인해야한다.

현재 비트에는 지금까지 방문한 도시의 정보가 담겨 있다.

만약 현재 비트가 15라면, 이진법으로 표기했을 때 1101이 되고 1, 3, 4번째 도시를 방문했다는 정보가 된다.

Bottom-Up코드의 목적은 정보를 끼워 맞추는 형태이기 때문에 이 비트에 이전 도시 자리가 1이어야 한다.

따라서 이전에 방문한 도시로 3을 넣어보려고 한다면 비트가 다음과 같은 형태여야 한다. (x1xx)

 

2번을 체크하기 위해서 입력값을 확인한다.

갈 수 없는 경우 0으로 표기되므로 이 부분만 체크하면 된다.

if ((bit & (1 << prev)) != 0 && cur != prev && matrix[prev][cur] != 0)

 

위의 과정을 거쳐 방문한 이전도시와 현재 도시에 대한 정보를 얻게 되었고,

이제 이 정보를 가지고 최소 비용을 업데이트 해 주면 된다.

이전 도시의 정보에 (이전 도시 -> 현재 도시)로 이동하는 비용을 더해준다.

이 때 유의해야 할 점은 비트에는 현재 도시에 대한 정보도 존재하기 때문에 XOR연산으로 현재 도시에 대한 정보를 비트에서 제해야한다.

dp[cur][bit] = Math.min(dp[cur][bit], dp[prev][bit ^ (1 << cur)] + matrix[prev][cur]);

 

모든 비트에 대한 검사를 완료하면 dp[x][최대 비트]에는 0번째 도시에서 모든 도시를 거쳐 x번째 도시에 도달하는데 최소 비용이 저장된다.

우리는 이 x번째 도시에서 0번째 도시로 다시 돌아오는 한 가지 과정을 더 거쳐야 한다.

쉽게 dp[x][최대 비트]에 matrix[x][0]을 더해주면 된다.

이 때, x에서 0번째 도시로 가는 길이 없는 경우만 체크하면 된다.

int result = INF;
for (int i = 1; i <n; i++) {
    if (matrix[i][0] != 0)
        result = Math.min(result, dp[i][MAX] + matrix[i][0]);
}

---

2. Top-Down

dp[n][bit] = 아직 방문하지 않은 모든 도시를 돌아 다시 n번째 도시로 돌아올 때 최소 비용

핵심적인 알고리즘을 제외하고 초기화하는 부분을 먼저 말하자면,

방문하지 않은 도시 = -1

방문했지만 길이 있지 않은 도시 = INF

로 초기화를 해 주어야 한다.

이 이유는 핵심적인 알고리즘을 설명하면서 다시 나오므로 그 때 알 수 있다.

 

if ((curBit & (1 << i)) == 0 && matrix[curCity][i] != 0) {
    dp[curCity][curBit] = Math.min(dp[curCity][curBit], matrix[curCity][i] + dfs(i, (curBit | 1 << i)));
}

위 if문의 조건은 Bottom-Up과 유사하지만 Bottom-Up과 다르게 prevCity가 아닌 nextCity를 체크하기 때문에 현재 도시에서 다음으로 갈 도시를 방문했는지 여부를 확인한다.

그러므로 다음 도시를 방문하지 않았다면 코어 알고리즘으로 들어가게 된다.

 

Top-Down은 현재 가지고 있는 정보에 계속해서 다음 도시의 정보를 더해가는 것이 목적이다.

따라서 현재 비트에 다음 도시의 정보를 OR연산으로 추가해나가며 계속해서 깊숙이 확인을 하러 내려간다.

 

if (dp[curCity][curBit] != -1) return dp[curCity][curBit];
dp[curCity][curBit] = INF;

이제 이 부분에서 초기화를 왜 이렇게 했는지 알 수 있다.

첫 if문은 '방문을 했다는 것'을 의미한다.

길이 있던지 없던지 상관없이 이미 방문을 했으므로 그 값을 리턴한다.

만약 길이 없어서 INF로 되어 있다면 이전 dfs에서 MIN연산을 하므로 상관없다.

 

그리고 이 유효성 검사 이후에는 실제 알고리즘을 수행해야 하며 여기서 길 존재 여부를 판단해주어야 하기 때문에 INF로 업데이트를 해 준다.

길이 있다면 이 부분은 INF가 아닌 다른 값으로 바뀔 것이고 길이 없다면 계속해서 INF일 것이다.

 

만약 이 두 가지 검사를 모두 하나의 상수인 INF로 한다면 어떻게 될까?

그럼 일단 위의 조건 검사 코드는 다음과 같이 변경된다.

if (dp[curCity][curBit] != INF) return dp[curCity][curBit];

초기화 또한 INF여서 방문여부를 확인할 때도 INF로 체크하고 길이 없을 때도 INF로 확인한다면

어떤 도시에서 다른 특정한 도시로 아예 갈 수 없는 상황일 때 왜 INF인지 이유를 알 수 없게 된다.

길이 없기 때문에 갈 수 없는지 아니면 아예 방문을 하지 않은 상태인지 알 수 없다.

따라서 길이 없어서 INF인 경우에도 계속 조건 검사 코드에 걸리지 않고 코어 알고리즘을 돌게 되어 무한적으로 dfs에 들어가게 된다.

 

Bottom-Up과 다르게 Top-Down은 dp[curCity][MAX]에서 이미 답을 구할 수 있다.

정의처럼 다른 도시를 모두 돌고 돌아온 값이 이 dp에 저장되기 때문이다.

---

이 문제는 사실 Bottom-Up방식이 생각하기 더 쉬웠던게 분기가 그렇게 많지도 않고 점점 갈수록 분기가 많아지는 구조가 아니기 때문이었다.

하지만 Bottom-Up의 경우 '이 도시까지'에 대한 정보만 들고 있기 때문에 한 번 더 계산을 해 주어야 한다는 수고가 따른다.