[c++][java][백준 2098] 외판원 순회

백준 2098번: 외판원 순회 [Gold 1]
https://www.acmicpc.net/problem/2098

2098번: 외판원 순회

문제 풀이

• 이 문제는 TSP (Traveling Salesperson Problem) 알고리즘 문제로 그래프의 모든 노드를 한 바퀴 순회하는 최적의 경로를 찾아내는 알고리즘입니다.
• 모든 노드를 순회하는 최적의 경로는 완전 탐색으로도 해결이 가능하지만 노드의 개수가 10개가 넘어간다면 시간 초과에 걸리게 됩니다. 이 문제는 노드의 최대 개수가 16개이기 때문에 Memoization을 적용해야 합니다.

int memo[16][1<<16]; // 현재 노드, 노드 방문 상태

 

• 문제에는 "어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로"라고 적혀있기 때문에 각 마을에서 모두 출발해 보면서 경로를 찾아야 할 것 같지만 실제로는 한 마을에서만 순회 경로를 찾게 되면 모두 같은 경로이기 때문에 모든 마을에서 출발할 필요가 없습니다!

 

코드 (c++)

#include <cstdio>
#include <algorithm>

using namespace std;

const int INF = 1e9;

int N, END;
int arr[16][16];
int memo[16][1<<16];

int tsp(int city, int visited) {
    // 마지막 노드에서 출발 지점으로 이동
    if(visited == END) return arr[city][0];

    // 현재 상태를 이미 계산한 값이 있다면 사용
    if(memo[city][visited] != INF) return memo[city][visited];

    // 값이 없다면 계산
    for(int i=0; i<N; ++i) {
        if(visited & (1 << i)) continue;

        if(arr[city][i]) {
            int res = tsp(i, visited | (1 << i));
            if(res) memo[city][visited] = min(memo[city][visited], res + arr[city][i]);
        }
    }

    return memo[city][visited];
}

int main() {
    scanf("%d", &N);
    END = (1 << N) - 1;

    for(int i=0; i<N; ++i) {
        for(int j=0; j<N; ++j) {
            scanf("%d", &arr[i][j]);
        }

        for(int j=0; j<(1<<N); ++j) {
            memo[i][j] = INF;
        }
    }

    int ans = tsp(0, 1);
    printf("%d\n", ans);

    return 0;
}

실행 결과

 

코드 (Java)

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

// 백준 2098: 외판원순회
// TSP 알고리즘
public class 외판원순회 {

    static final int INF = (int) 1e9;
    static int[][] arr = new int[16][16];
    static int[][] memo = new int[16][1<<16];
    static int N, END;

    public static int tsp(int city, int visited) {
        if(visited == END) return arr[city][0];
        if(memo[city][visited] != INF) return memo[city][visited];

        for(int i=0; i<N; ++i) {
            if(arr[city][i] != 0 && (visited & (1 << i)) == 0) {
                int res = tsp(i, visited | (1 << i));

                if(res > 0)
                    memo[city][visited] = Math.min(memo[city][visited], res + arr[city][i]);
            }
        }

        return memo[city][visited];
    }

    public static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        END = (1 << N) - 1;

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

            Arrays.fill(memo[i], INF);
        }

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

실행 결과