[BOJ/TSP] 백준 2098 - 외판원 순회 / 10971 - 외판원 순회 2 (Java)

2098 - 외판원 순회

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

문제

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다 (길이 없을 수도 있음)
한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다
(단, 한 번 갔던 도시는 다시 갈 수 없음, 맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외)
이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우려고 함
각 도시간에 이동하는데 드는 비용: W[i][j] 도시 i에서 도시 j로 가기 위한 비용 (대칭적 X, W[i][j]는 W[j][j]와 다를 수 있음) 
모든 도시간의 비용은 양의 정수, W[i][i] = 0 / 경우에 따라 도시 i에서 도시 j로 갈 수 없는 경우도 O -> W[i][j] = 0

=> N과 비용 행렬이 주어졌을 때 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램

입력
첫째 줄: 도시의 수 N (2 <= N <= 16)
다음 N개의 줄: 비용 행렬 (행렬의 선분 (양의 정수) <= 1,000,000, 갈 수 없는 경우 0)
항상 순회할 수 있는 경우만 입력으로 주어짐
출력: 외판원의 순회에 필요한 최소 비용?

---

풀이

외판원 순회(TSP; Traveling Salesperson Problem)

• N개의 도시가 있고, 각 도시를 한 번씩만 방문한 뒤, 다시 출발 도시로 돌아오는 최단 경로를 구하는 문제
  • 모든 도시를 한 번씩 들르고 / 다시 출발 도시로 돌아오는 / 최단 거리 or 최소 비용의 순회 경로
• 경우의 수: (N-1)! / 2 
  • 출발 도시 고정, 순회 -> 대칭인 경로 제거 가능
• DP + 비트마스크(동적 계획법)
  • 가장 대표적인 효율적인 풀이 
  • DP: 현재 도시와 방문 상태 조합에 대해 최단 경로 비용을 메모제이션
    • `dp[current][visited] = 최소 비용` -> 현재 `current` 도시에서 `visited` 도시 집합 상태일 때
      남은 도시를 모두 방문하고 시작 도시로 돌아가는 최소 비용
  • 비트마스크: 방문한 도시들을 집합 형태로 표현(0 ~ N까지 2진수로 표현)
    • ex. `visited = 01101` -> 5개 도시 중 0, 2, 3번 도시 방문한 상태
  • 시간복잡도: $O(N^2 * 2^N)$
    • N >= 16 -> 출발점 고정 필요: `tsp(0, 1 << 0)`

 

• `dp = new int[N][1 << N]`: 1 << N == $2^N$
  • N개의 도시가 있을 때 가능한 방문 상태 조합의 수
  • ex. N = 3 -> 1 << 3 = 8 => 000 ~ 111까지 총 8가지($2^3$)
• `dp[cur][visited] = 최소 비용`
  • `Arrays.fill(dp[i], -1)`: 아직 계산하지 X 상태는 -1로 초기화 

for (int i = 0; i < N; i++) {
    Arrays.fill(dp[i], -1);
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int j = 0; j < N; j++) {
        W[i][j] = Integer.parseInt(st.nextToken());
    }
}

System.out.println(tsp(0, 1));

 

• 모든 도시 방문했는지 검사
  • `(1 << N) - 1`: 111...1 (N자리) ==`visited == 2^N - 1` -> 모든 도시 방문 완료
  • ex. N = 3 -> (1 << 3) - 1 = 8 - 1 = 7 = 111(2진수)

• 모든 도시 방문 O -> 시작 도시(0번)으로 돌아가는 비용 반환
  • `W[cur][0] == 0`: 현재 도시 `cur`에서 0번 도시로 돌아갈 수 X -> `INF` => 해당 경로 무시

if (visited == (1 << N) - 1) {
    return W[cur][0] == 0 ? INF : W[cur][0];
}

• `dp[cur][visited] != -1`: 이미 `(cur, visited)` 상태 계산 O => 저장된 값(`dp`) 재사용

if (dp[cur][visited] != -1) return dp[cur][visited];

• 현재 도시에서 다음 방문할 수 있는 모든 도시 확인
  
  • next 도시가 방문 X 도시 + 경로 O -> next 도시 방문 기록
    
    • `(vsited & (1 << next)) == 0 && W[cur][next] != 0`
  • 비용: (현재 도시 ~ next 도시) 비용 + (next 도시 ~ 남은 도시) 비용 
    
    • `W[cur][next] + tsp(next, newVisited)`
    • `int newVisited = visited | (1 << next)`: 현재 방문(visited) 상태에서, next 도시 방문
      
      • `1 << next` == `2^next`: next 번째 비트만 1인 값
        • ex. next = 0 -> `1 << next` = 1 -> 0001(2진수)
          / next = 1 -> `1 << next` = 2 -> 0010(2진수)
      • `visited | (1 << next)`: 기존 방문 상태에 next 도시 방문을 추가
      • ex. next = 2 -> `1 << next` = 4 -> 0100
        -> `visited(0011) | (1 << next)(0100)` => 0111 -> 0, 1, 2번 도시 방문한 상태

int minCost = INF;
for (int next = 0; next < N; next++) {
    if ((visited & (1 << next)) == 0 && W[cur][next] != 0) {
        int newVisited = visited | (1 << next);
        int cost = W[cur][next] + tsp(next, newVisited);
        minCost = Math.min(minCost, cost);
    }
}

return dp[cur][visited] = minCost;

---

코드

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

// 외판원 순회
public class boj_2098 {
    static int N;
    static int[][] W;
    static int[][] dp;
    static final int INF = 1_000_000_000;

    static int tsp(int cur, int visited) {
        if (visited == (1 << N) - 1) {
            return W[cur][0] == 0 ? INF : W[cur][0];
        }

        if (dp[cur][visited] != -1) return dp[cur][visited];

        int minCost = INF;
        for (int next = 0; next < N; next++) {
            if ((visited & (1 << next)) == 0 && W[cur][next] != 0) {
                int newVisited = visited | (1 << next);
                int cost = W[cur][next] + tsp(next, newVisited);
                minCost = Math.min(minCost, cost);
            }
        }

        return dp[cur][visited] = minCost;
    }

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

        N = Integer.parseInt(br.readLine());
        W = new int[N][N];
        dp = new int[N][1 << N];

        for (int i = 0; i < N; i++) {
            Arrays.fill(dp[i], -1);
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                W[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        System.out.println(tsp(0, 1));
    }
}

---

10971 - 외판원 순회 2

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

문제

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다 (길이 없을 수도 있음)
한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다
(단, 한 번 갔던 도시는 다시 갈 수 없음, 맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외)
이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우려고 함
각 도시간에 이동하는데 드는 비용: W[i][j] 도시 i에서 도시 j로 가기 위한 비용 (대칭적 X, W[i][j]는 W[j][j]와 다를 수 있음) 
모든 도시간의 비용은 양의 정수, W[i][i] = 0 / 경우에 따라 도시 i에서 도시 j로 갈 수 없는 경우도 O -> W[i][j] = 0

=> N과 비용 행렬이 주어졌을 때 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램

입력
첫째 줄: 도시의 수 N (2 <= N <= 10)
다음 N개의 줄: 비용 행렬 (행렬의 선분 (양의 정수) <= 1,000,000, 갈 수 없는 경우 0)
항상 순회할 수 있는 경우만 입력으로 주어짐
출력: 외판원의 순회에 필요한 최소 비용?

---

풀이

모든 도시를 출발점으로 시도

int answer = INF;
for (int i = 0; i < N; i++) {
    dp = new int[N][1 << N];
    for (int[] row : dp) Arrays.fill(row, -1);

    answer = Math.min(answer, tsp(i, i, 1 << i));
}

---

코드

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

// 외판원 순회 2
public class boj_10971 {
    static int N;
    static int[][] W;
    static int[][] dp;
    static final int INF = 1_000_000_000;

    static int tsp(int start, int cur, int visited) {
        if (visited == (1 << N) - 1) {
            return W[cur][start] == 0 ? INF : W[cur][start];
        }

        if (dp[cur][visited] != -1) return dp[cur][visited];

        int minCost = INF;
        for (int next = 0; next < N; next++) {
            if ((visited & (1 << next)) == 0 && W[cur][next] != 0) {
                int newVisited = visited | (1 << next);
                int cost = W[cur][next] + tsp(start, next, newVisited);
                minCost = Math.min(minCost, cost);
            }
        }

        return dp[cur][visited] = minCost;
    }

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

        N = Integer.parseInt(br.readLine());
        W = new int[N][N];

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

        int answer = INF;
        for (int i = 0; i < N; i++) {
            dp = new int[N][1 << N];
            for (int[] row : dp) Arrays.fill(row, -1);

            answer = Math.min(answer, tsp(i, i, 1 << i));
        }

        System.out.println(answer);
    }
}