Lewis's Tech Keep
[백준] 외판원 순회 본문
참고 : www.acmicpc.net/problem/2098
- dp문제
- 답 보고 풀었다..
- dp + 비트마스크 문제
- ex) n= 4일 때 bit : 1111 (15) 를 모든 정점을 방문했다고 생각
- dp[node][visit] 일 때의 최소값을 구해주면 된다. (for로 모든 노드에서 출발했을 때 dfs로 탐색)
더보기
import java.io.*;
import java.util.Arrays;
import java.util.Scanner;
public class Solution {
private static int[][] arr;
private static int[][] dp;
private static int N;
private static int INF = 16 * 1_000_000;
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
arr = new int[N][N];
dp = new int[N][(1<<N)-1];
for (int i = 0; i < N; i++) {
Arrays.fill(dp[i], INF);
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
arr[i][j] = sc.nextInt();
}
}
System.out.println(tsp(0, 1));
}
private static int tsp(int node, int visit) {
if(visit == (1<<N) -1) {
if(arr[node][0] == 0) return INF;
return arr[node][0];
}
// 이미 지나간 노드값이라면 그대로 return
if(dp[node][visit] != INF) return dp[node][visit];
for (int i = 0; i < N; i++) {
int next = visit | (1<<i);
// 이미 0으로 가는 것이 불가능 하거나
// visit에 이미 ex) 0011 0010 -> 1 이미 들렀던 곳이거나
if(arr[node][i] == 0 || (visit & (1<<i)) != 0) continue;
// dp[node][visit]의 현재 비용 tsp (현재까지 이동하는 비용 ) + 0으로 이동하는 비용
dp[node][visit] = Math.min(dp[node][visit], tsp(i, next) + arr[node][i]);
}
return dp[node][visit];
}
}
'JAVA > 알고리즘' 카테고리의 다른 글
[프로그래머스] 브라이언의 고민 (0) | 2021.04.15 |
---|---|
[프로그래머스] 풍선 터트리기 (0) | 2021.04.15 |
[백준] 고층 빌딩 (0) | 2021.04.13 |
[백준] 극장 좌석 (0) | 2021.04.12 |
[프로그래머스] 길찾기 게임 (0) | 2021.04.12 |
Comments