[Algorithm] 백준 DP 문제 - 외판원 순회(2098) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 외판원 순회 자바 풀이를 진행하고자 합니다.

문제 출처: https://www.acmicpc.net/problem/2098

2098번: 외판원 순회

 

1. 풀이 소스

 

import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;

public class Main {
    static int n;
    static int answer;
    static int[][] fromTo;
    static int [][] dp;
    static int INF = 987654321;

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

        n = parseInt(br.readLine());
        fromTo = new int[n][n];
        dp = new int[1 << n][n]; // 디피 설정

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) fromTo[i][j] = parseInt(st.nextToken());
        }

        answer = tsp(1, 0); // 방문, 위치
        System.out.println(answer);
    }

    static int tsp(int visited, int loc) {
        if (visited == (1 << n) - 1) {
            if (fromTo[loc][0] > 0) return fromTo[loc][0]; // 값이 유효함
            return INF; // 간선이 없어서 최대값으로 설정
        }

        if (dp[visited][loc] > 0) return dp[visited][loc]; // 현재 방문한 상태가 최신 상태로 업데이트 된 경우

        dp[visited][loc] = INF; // 아직 방문하지 않았음을 의미함

        for (int dest = 0; dest < n; dest++) {
            if (isValid(visited, loc, dest))
                dp[visited][loc] = Math.min(dp[visited][loc],
                        tsp(visited | (1 << dest), dest) + fromTo[loc][dest]);
        }

        return dp[visited][loc];
    }

	// 비트마스크의 & 연산으로 아직 방문하지 않은 경우 == 같은 위치에 1이 존재하지 않는 경우 == 0 && 방문 하려는 곳의 간선이 존재
    static boolean isValid(int visited, int loc, int dest) {
        return (visited & (1 << dest)) == 0 && fromTo[loc][dest] > 0;
    }
}

 

2. TSP (Traveling Salesman Problem)

 

TSP는 외판원 문제로 외판원이 각 독시를 정확히 한 번씩 방문하고, 처음 출발한 도시로 돌아오는 가장 짧은 경로는 무엇인지 구하는 문제입니다. 이 문제는 NP-완전 문재로 모든 가능한 경우를 탐색하여 최적 해를 구할 수 있습니다. 

 

3. DP와 비트마스킹

 

DP와 비트마스킹으로 TSP 문제를 해결할 수 있습니다. DP를 사용할 경우 시간 복잡도는 O(N^2 * 2^N)으로 해결할 수 있습니다.

• N^2: 모든 도시 간의 거리를 계산하는데 필요한 시간을 나타냅니다. 각 도시에서 다른 모든 도시로 이동하는 비용을 확인하는 단계입니다.
• 2^N: 각 도시의 방문 상태를 고려해야 합니다. 비트마스킹을 사용하므로 2^N으로 (ex 010100) 형태로 각 방문 상태를 설정할 수 있습니다. 

이러한 방법을 토대로 브루트 포스 방법으로 탐색할 경우 가지는 N! 보다 빠른 속도로 탐색을 수행할 수 있습니다.

 

N개의 노드가 있을 때, 방문 상태를 1 << N의 비트로 관리하면 방문 상태를 유지할 수 있습니다.

0010의 경우 2번 인덱스 노드는 방문한 상태를 의미하고, 0011은 2, 3번 노드를 방문한 상태를 의미합니다.

 

visited | (1 << n); // n을 방문 처리
visited & (1 << n); // n이 방문을 했는지 안했다면 0

 

자바에서 비트의 OR은 '|' 로 계산할 수 있습니다.

0010 | 0100 = 0110 을 구할 수 있습니다.

 

AND 연산은 '&'로 구할 수 있습니다. 같은 위치에 1이 있어야 1이 인정됩니다.

0010 & 0100 = 0000 

 

이를 토대로 visited | (1 << n)을 해석하면,

현재 방문한 상태의 visited 값과 or 연산을 진행하는데, 대상은 1 << n입니다.

1 << n은 1에서 n개까지를 오른쪽으로 시프트 시키는 것을 의미합니다. 즉,

1 << 3 = 1000(2)를 의미하는 것입니다. 

 

만약 visited = 10000(2) 였다면, visited | (1 << n)은 11000(2)의 값을 가질 수 있습니다.

AND연산은 방문을 이미 했는지를 판단해야 하므로 같은 위치에 1이 있는지를 판단하게 됩니다. 만약 0이라면
같은 자리에 1이 없다는 것을 의미하므로 방문하지 않았음을 의미합니다. 

 

한 가지 의문점은 왜 굳이 비트마스킹으로 visited를 설정하는가입니다

이는 비트열로 visited를 수정하고 바꾸는 과정을 수행하므로 따로 boolean 배열을 설정하지 않더라도 문제를 해결할 수 있습니다. 

또한 비트는 다른 연산보다 더 빠르게 연산이 가능하므로 효율적으로 계산을 수행할 수 있습니다.

 

 

4. 풀이 중점 사항

 

이를 토대로 코드를 살펴보면 다음과 같습니다.

TSP 문제를 해결하기 위해 DP와 비트마스킹을 활용합니다. 0, 0의 정점에서 시작하여 각 정점까지 이동이 가능한지 파악하고 방문하지 않았다면 방문합니다. 방문한 노드에서 현재 모두 방문해서 마지막 다시 시작점으로 이동해야 하는지, 혹은 이전에 이미 값을 업데이트했는지 등을 파악합니다. 이러한 재귀를 마치게 되면, 최종적으로 가장 짧은 순회 길이를 구할 수 있습니다.

 

          1열       2열      3열

1행     0           1          2

2행     1           0          1

3행     0           0          0

 

이 상태에서 예를 들어 (0, 0)으로 시작을 하면, (0,1)을 거치게 됩니다.

(1, 3) 열을 거치게 되고 (3, 1) 열을 거쳐서 값을 리턴하는 방식으로 재귀형태로 진행이 됩니다.

 

static int tsp(int visited, int loc) {
        if (visited == (1 << n) - 1) {
            if (fromTo[loc][0] > 0) return fromTo[loc][0]; // 값이 유효함
            return INF; // 간선이 없어서 최대값으로 설정
        }

        if (dp[visited][loc] > 0) return dp[visited][loc]; // 현재 방문한 상태가 최신 상태로 업데이트 된 경우

        dp[visited][loc] = INF; // 아직 방문하지 않았음을 의미함

        for (int dest = 0; dest < n; dest++) {
            if (isValid(visited, loc, dest))
                dp[visited][loc] = Math.min(dp[visited][loc],
                        tsp(visited | (1 << dest), dest) + fromTo[loc][dest]);
        }

        return dp[visited][loc];
    }

// 비트마스크의 & 연산으로 아직 방문하지 않은 경우 == 같은 위치에 1이 존재하지 않는 경우 == 0 && 방문 하려는 곳의 간선이 존재
static boolean isValid(int visited, int loc, int dest) {
    return (visited & (1 << dest)) == 0 && fromTo[loc][dest] > 0;
}

 

저는 55%에서 에러가 발생하여 참고한 블로그를 토대로 코드를 작성했었습니다.

중요한 포인트는 저는 시작할 때, 모두 INF값으로 설정하여, 간선이 없는 경우에도 INF 처리가 되어 에러가 발생했습니다.

참고했던 블로그 소스들에서는 시작을 모두 0으로 초기화하고, 간선이 존재하지 않으면 INF를 리턴합니다.

이렇게 되면, 자연스럽게 Math.min()의 우선순위에서 밀려서 선택이 되지 않고, 방문하지 않았고 간선이 존재하는 경우
INF로 초기화하고 loc위치에서 이동하려는 dest로 다시 tsp 재귀를 진행하면 간선이 존재하는 경우는 INF보다 작으므로 선택될 수 있는 환경이 되었습니다.

 

 

answer = tsp(1, 0); // 방문, 위치

처음 문제를 해결할 때, 왜 0번 인덱스로 순회를 시작하면 되는가에 대한 의문이 있었습니다.

순회라는 개념은 사이클이 된다는 것을 의미합니다.

 

만약, 최단 거리를 유지할 수 있는 순회 경로가

0 -> 1 -> 2 -> 3 -> 0이라면,

1-> 2 -> 3 -> 0 -> 1과 동일합니다.

 

즉 어디서 시작하던 0 -> 1을 가야 하고, 1 -> 2를 가야하고 , 2 -> 3, 3 -> 0을 가는 것은 동일합니다.

 

만약 최단 거리를 유지할 수 있는 순회 경로가

1 -> 2 -> 0 -> 3 -> 1 이더라도

0 -> 3 -> 1 -> 2 -> 0 은 순서만 다를 뿐 실제 사이클은 동일합니다.

따라서, 이 원리를 토대로 0번 인덱스에서 시작하면 최적의 값을 구할 수 있습니다.

 

외판원 문제와 같은 비트마스크 연산은 항상 헷갈리는데 나올 때마다 정리해 놓으면 도움이 되는 것 같습니다. 이상으로 

외판원 순회 자바 풀이를 마치도록 하겠습니다.

 

참고 블로그: https://velog.io/@zeesouth/%EB%B0%B1%EC%A4%80-2098.-%EC%99%B8%ED%8C%90%EC%9B%90-%EC%88%9C%ED%9A%8C-Java