2098번 외판원 순회

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

외판원 순회문제이다.

나중에 풀어볼 문제 : https://www.acmicpc.net/problem/10849

JAVA 코드도 첨부

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 16 // 0번 도시 ~ 15번 도시
#define INF 987654321
 
int W[Max][Max], cache[1 << Max][Max], n;
 
/*
W[i][j] = i번 정점에서 j번 정점으로 가는 비용. 즉, i는 현재 정점, j는 다음 정점
cache[i][j] = i는 지금까지 방문한 정점들, j는 현재 정점
*/
 
int tsp(int visitedPath, int now)
{
    // 기저 : 모든 정점을 다 방문했을 때
    if (visitedPath == (1 << n) - 1)
    {
        if (W[now][0] != 0) // 다시 원점인 0번 정점으로 되돌아 갈 수 있다면
            return W[now][0]; // W[0][now]가 아니다.
        return INF; // 되돌아가지 못 하는 경우
    }
 
    int &result = cache[visitedPath][now];
 
    if (result != -1) return result;
 
    result = INF;
 
    for (int next = 0; next < n; next++)
    {
        // 이미 경로(visitedPath)에 해당 next가 있거나 now에서 next로 가는 비용이 0이면 무시
        if (visitedPath & (1 << next) || W[now][next] == 0) 
            continue;
        result = min(result, W[now][next] + tsp(visitedPath | (1 << next), next));
    }
 
    return result;
}
 
int main(void)
{
    memset(cache, -1, sizeof(cache));
 
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)        
            scanf("%d", &W[i][j]);
 
    cout << tsp(1, 0) << '\n';
 
    return 0;
}

import java.io.*;
import java.util.*;
 
public class Main {
    
    static int w[][], cache[][];
    static int n;
    static final int INF = 987654321;
    
    static int tsp(int now, int path)
    {
        // 마지막 정점까지 왔다면
        if(path == (1 << n) - 1) {
            if(w[now][0] == 0) return INF;
            return w[now][0];
        }
        
        // -1이 아니라면, 이미 방문한 적이 있음
        if(cache[now][path] != -1 ) return cache[now][path];
        
        int ret = INF;
 
        // 모든 거점 조사
        for(int i = 0; i < n; i++) {
            if((path & (1 << i)) != 0 || w[now][i] == 0) continue;
            ret = Math.min(ret, w[now][i] + tsp(i, path | (1 << i)));
        }
        
        // 구한 최소의 ret return
        return cache[now][path] = ret;
    }
    
    public static void main(String[] args) throws IOException 
    {
        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];
        cache = new int[n][(1 << n)];    
        
        for(int i = 0; i < n; i++) {
            Arrays.fill(cache[i], -1);
        }
        
        for(int i = 0; i < n; i++) {
            StringTokenizer temp = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++) {
                w[i][j] = Integer.parseInt(temp.nextToken());
            }
        }
        
        System.out.print(tsp(0, 1) + "\n");
    }
}