[Java] 백준 2098번 외판원 순회

외판원 순회 문제입니다.
외판원이 모든 도시를 한번씩만 거쳐서 출발한 도시로 다시 돌아올 때 최소 비용을 구해야합니다.

DFS 탐색을 하고 방문처리에 대해서 비트로 처리합니다.
방문한 경우에 대해서 DP를 사용해서 값을 저장해줍니다.

DP[bit][loc]로 저장하며, 해당 bit와 loc(현재 위치)로 안에 최적의 비용을 담고 있습니다.

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

public class Main {
	static int n;
	static int ans;
	static int[][] map;
	static int[][] dp;
	static int INF = 987654321;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		map = new int[n][n];
		dp = new int[1 << n][n];

		for (int i = 0; i < n; ++i) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; ++j) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		ans = TSP(0, (1 << 0)); // 위치, bit

		bw.write(ans + "");
		bw.close();
	}

	public static int TSP(int loc, int bit) {
		if (bit == (1 << n) - 1) {
			if (map[loc][0] > 0) {
				return map[loc][0];
			}
			return INF;
		}

		if (dp[bit][loc] > 0) {
			return dp[bit][loc];
		}
		dp[bit][loc] = INF;

		for (int i = 0; i < n; ++i) {
			if ((bit & (1 << i)) == 0 && map[loc][i] > 0) { // 방문 안 한 경우
				dp[bit][loc] = Math.min(dp[bit][loc], TSP(i, bit | (1 << i)) + map[loc][i]);
			}
		}

		return dp[bit][loc];
	}
}