[Java] 백준 2098 외판원 순회 - dp, bitmasking

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

2098번: 외판원 순회

 

오랜만에 이산수학 책을 폈다 ㅎㅎ

- 해밀턴 경로 : 그래프의 점을 모두 방문하되, 중복하여 방문하지 않고 모든 점을 지나는 경로. (1->2->3->4)

- 해밀턴 순환 : 그래프의 점을 모두 방문하고, 중복하여 방문하지 않으며, 처음 시작 점으로 돌아오는 경로. (1->2->3->4->1)

순환이기에 모든 점을 출발점으로 외판원 순회 경로를 계산하지 않아도 된다. 한 점에서의 외판원 순회 경로를 생각해주면 그게 정답이다. 1>3>2>1과 2>1>3>2는 동일하다.

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

public class Main {
    static int n;   // 도시의 개수
    static int[][] w, dp;
    static final int INF = 16_000_000;

    // dfs: current 도시에서 방문하지 않은 도시를 모두 방문하고 처음 도시(0)으로 돌아가는 데 소요되는 최소 비용
    public static int dfs(int current, int visited){
        // 마지막 도시 -> 처음 도시
        if(visited == (1<<n) - 1){  // 모든 도시를 방문함.
            if(w[current][0] != 0){ // 가는 길이 있다면
                return w[current][0];
            }else{  // 순회 불가능
                return INF;
            }
        }

        if(dp[current][visited] != -1){ // 이미 계산한 적이 있으면
            return dp[current][visited];
        }

        dp[current][visited] = INF;

        for(int i=0; i<n; i++){
            // 현재 도시에서 i 도시까지 갈 수 있고, i 도시를 방문하지 않았으면 방문한다.
            if(w[current][i] != 0 && (visited & (1<<i)) == 0){
                dp[current][visited] = Math.min(dp[current][visited], w[current][i] + dfs(i, (visited | (1<<i))));
            }
        }

        return dp[current][visited];
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        w = new int[n][n];
        String[] line;

        for(int i=0; i<n; i++){
            line = br.readLine().split(" ");
            for(int j=0; j<n; j++){
                w[i][j] = Integer.parseInt(line[j]);
            }
        }

        dp = new int[n][1<<n];  // dp[i][방문한도시] = 현재 도시 i로부터 방문하지 않은 도시들을 지나 시작 도시로 순회하는 데 소요되는 비용
        for(int[] arr: dp){
            Arrays.fill(arr, -1);   // 방문하지 않은 점은 -1로 처리
        }

        int result = dfs(0, 1);
        System.out.println(result);
    }
}

• 방문한 점을 Integer.MAX_VALUE로 지정하면 오버플로우가 발생하여 INF 즉, 16점*1,000,000 으로 지정해야 한다.

dp[current][visited] = INF;

이 부분을 반드시 이렇게 지정해야 하는지 의문이 들었다.

dfs(i, (visited | (1<<i))

여기에서 i 도시를 방문했다고 설정해주는데 굳이 해주어야 하나 생각했다.

그래서

int min = INF;

for(int i=0; i<n; i++){
    // 현재 도시에서 i 도시까지 갈 수 있고, i 도시를 방문하지 않았으면 방문한다.
    if(w[current][i] != 0 && (visited & (1<<i)) == 0){
        min = Math.min(min, w[current][i] + dfs(i, (visited | (1<<i))));
    }
}

dp[current][visited] = min;

return dp[current][visited];

이렇게 바꾸어 봤는데 이렇게 해도 정답이다.

오히려 시간이 단축됐다..

 

 

윗 줄이 바꾼 것

아랫 줄이 INF 대입한 것

---

- 오답 코드

순수 dfs로 구현했는데 왜 오답이 나올까??????? 너무 궁금한데....

일단 마지막 도시에서 처음 도시로 순환할 수 없다는 가능성을 배제했기에 틀렸다.

package Bj_2098;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int n;   // 도시의 개수

    // dfs: 현재 도시 -> 시작 도시 까지 소요되는 최소 비용을 반환하는 함수
    // 시작 도시, 현재 도시, 지나온 도시 목록, 누적 비용, 비용 행렬
    public static int dfs(int start, int current, boolean[] visited, int cost, int[][] w, int depth){
        // 마지막 도시 -> 처음 도시
        if(depth == n-1){
            return cost + w[current][start];
        }

        int min = Integer.MAX_VALUE;

        for(int i=0; i<n; i++){
            // 비용이 0이 아니고, 방문하지 않은 도시를 방문한다.
            if(!visited[i] && w[current][i] != 0){
                visited[i] = true;
                min = Math.min(min, cost + w[current][i] + dfs(start, i, visited, cost + w[current][i], w, depth + 1));

                visited[i] = false;
            }
        }

        return min;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        int[][] w = new int[n][n];
        String[] line;

        for(int i=0; i<n; i++){
            line = br.readLine().split(" ");
            for(int j=0; j<n; j++){
                w[i][j] = Integer.parseInt(line[j]);
            }
        }

        int result = Integer.MAX_VALUE;
        boolean[] visited = new boolean[n];
        for(int i=0; i<n; i++) {
            visited[i] = true;
            result = Math.min(result, dfs(i, i, visited, 0, w, 0));
            visited[i] = false;
        }

        System.out.println(result);
    }
}