2098 - 외판원 순회 (Java)

🔗 문제 링크

---

📝 문제 설명

외판원 순회 문제(Travelling Salesman Problem)는 모든 도시를 한 번씩 방문하고 시작 도시로 돌아오는 최소 비용 경로를 찾는 문제임.
이 문제는 NP-Hard 문제에 속하며, 비트마스킹과 동적 계획법(DP)를 이용한 기법이 주로 사용됨.

---

✅ 풀이 과정

1️⃣ 첫 번째 시도: DFS + 비트마스킹 + 3차원 DP

접근법:

• DFS를 사용하여 모든 경로를 탐색하고, 방문한 도시들을 비트마스킹으로 관리함.
• 3차원 DP 배열을 사용하여 dp[start][end][visited]로 상태를 저장함.
• 문제점:
  • 모든 출발점을 고려하여 탐색했음으로 인해 상태 공간이 너무 커짐,
  • 결과적으로 시간 초과가 발생하였음.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static StringTokenizer st;
    private static StringBuilder sb = new StringBuilder();
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private static int N;
    private static int[][] connInfo;
    private static int[][][] dp;
    private static int answer = 1000000000;

    public static void main(String[] args) throws IOException {
        setting();
        for (int i = 0; i < N; i++) {
            dfs(i, i, (1 << i), 0);
        }
        System.out.println(answer);
    }

    private static void dfs(int start, int end, int visited, int result) {
        // 이미 더 작은 비용으로 탐색한 경우 시간 단축
        if (result >= dp[start][end][visited]) {
            System.out.println("시간단축");
            return;
        }
        dp[start][end][visited] = result;
        if (visited == (int) Math.pow(2, N) - 1) {
            answer = Math.min(answer, result + connInfo[end][start]);
        }

        for (int i = 0; i < N; i++) {
            int nextNum = i;
            int nextVal = connInfo[end][i];
            if ((visited & (1 << nextNum)) != (1 << nextNum)) {
                // 아직 방문하지 않은 도시일 경우
                dfs(start, nextNum, visited | (1 << nextNum), result + nextVal);
            }
        }
    }

    private static void setting() throws IOException {
        N = Integer.parseInt(br.readLine());
        dp = new int[N][N][(int) Math.pow(2, N)];
        connInfo = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                connInfo[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                for (int k = 0; k < dp[0][0].length; k++) {
                    dp[i][j][k] = 1000000000;
                }
            }
        }
    }
}

결과: 시간 초과 발생
→ DFS로 거의 완전 탐색을 진행했음으로, 불필요한 반복 계산과 상태 공간이 너무 커진 것이 주 원인임.

---

2️⃣ 두 번째 시도: DFS + 비트마스킹 + 2차원 DP

문제 해결 아이디어:

• 모든 도시를 한 번씩 방문하는 경로는 출발 도시에 관계없이 동일한 결과값을 갖게 됨.
• 따라서, dp[현재 도시][방문 비트마스킹] 형태의 2차원 DP 배열로 충분함.
• 중요한 점은 DP 테이블의 초기화와 메모이제이션 체크에 사용되는 값임.

문제의 원인 분석:

두 가지 구현 방식의 차이는 다음과 같음.

1. 정답 코드 (효율적)

   • DP 배열 초기화: 모든 값을 NOT_INITIALIZE (-1)로 초기화하여 아직 계산되지 않은 상태임을 명확하게 구분함.
   • 메모이제이션 체크:

     if (dp[cur][visited] != NOT_INITIALIZE) {
         return dp[cur][visited];
     }
     dp[cur][visited] = 1000000000;

   • 즉, 미계산 상태를 -1로 구분하고, 실제 계산 값이 1000000000일 수 있어도 이를 명확하게 구분할 수 있음.

2. 시간 초과 코드 (비효율적)

   • DP 배열 초기화: 모든 값을 MAX_RESULT (1000000000)으로 초기화함.
   • 메모이제이션 체크:

     if (dp[cur][visited] != MAX_RESULT) {
         return dp[cur][visited];
     }

   • 이 경우, 계산 결과가 1000000000일 때와 아직 계산되지 않은 상태를 구분할 수 없어서,
     불필요한 재귀 호출이 반복되어 시간 초과가 발생함.

---

최종 정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static StringTokenizer st;
    private static StringBuilder sb = new StringBuilder();
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private static int N;
    private static int[][] connInfo;
    private static int[][] dp;
    private static int NOT_INITIALIZE = -1;
    private static int MAX_RESULT = 1000000000;

    public static void main(String[] args) throws IOException {
        setting();
        System.out.println(dfs(0, 1));
    }

    private static int dfs(int cur, int visited) {
        if (visited == (1 << N) - 1) {
            if (connInfo[cur][0] == 0) return MAX_RESULT;
            else return connInfo[cur][0];
        }

        if (dp[cur][visited] != NOT_INITIALIZE) {
            return dp[cur][visited];
        }

        dp[cur][visited] = MAX_RESULT;

        for (int i = 0; i < N; i++) {
            if (connInfo[cur][i] != 0 && (visited & (1 << i)) == 0) {
                dp[cur][visited] = Math.min(dp[cur][visited], connInfo[cur][i] + dfs(i, visited | (1 << i)));
            }
        }
        return dp[cur][visited];
    }

    private static void setting() throws IOException {
        N = Integer.parseInt(br.readLine());
        dp = new int[N][(int) Math.pow(2, N)];
        connInfo = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                connInfo[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for (int i = 0; i < dp.length; i++) {
            for (int k = 0; k < dp[0].length; k++) {
                dp[i][k] = NOT_INITIALIZE;
            }
        }
    }
}

---

✅ 결론

• 초기 시도 (3차원 DP + DFS):
  출발점을 모두 고려하여 탐색했음으로 상태 공간이 과도하게 커져 시간 초과가 발생하였음.

• DP 초기화와 메모이제이션 체크의 중요성:

  • 비교 대상 값:
    • 정답 코드: if (dp[cur][visited] != -1) { ... } 후 dp[cur][visited] = MAX_RESULT;
    • 시간 초과 코드: if (dp[cur][visited] != MAX_RESULT) { ... }
  • 미계산 상태와 계산 결과를 명확하게 구분하지 않으면, 동일한 값(여기서는 1000000000)을 갖는 경우를 구분할 수 없어서 불필요한 재귀 호출이 반복됨.

• 최종 접근법:
  시작점을 고정하고, dp[현재 도시][방문 상태] = 최소 비용으로 처리하여 탐색의 범위를 줄임으로써 효율적으로 문제를 해결함.

---