💁♀️ 비트마스킹 + dp(TSP) 사용!
이 문제는 어떻게 풀어야할지 감이오지않았다.
Troublehsooting
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class makeOne {
private static final int INF = 1000000*16+1;
private static int N;
private static int[][] W;
private static int[][] d;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N = Integer.parseInt(br.readLine().trim());
W = new int[16][16];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine().trim());
for (int j = 0; j < N; j++) {
W[i][j] = Integer.parseInt(st.nextToken());
}
}
d = new int[16][1 << 16];
for (int i = 0; i < N; i++) {
for (int j = 0; j < 1 << N; j++) {
d[i][j] = INF; //모든 비용을 충분히 큰수로 저장
}
}
System.out.println(tsp(0, 1));
}
private static int tsp(int c, int v) { //모든 경우의 수에 대한 완전 탐색, 재귀 구현
if (v == (1 << N) - 1) { // 모든 노드를 방문한 경우
return W[c][0] == 0 ? INF : W[c][0];
}
if (d[c][v] != INF) { //이미 방문한 노드인 경우 -> 이미 계산한 경우 바로 리턴 (메모이제이션)
return d[c][v];
}
for (int i = 0; i < N; i++) {
if ((v & (1 << i)) == 0 && W[c][i] != 0) { //방문한적이 없고 갈 수 있는 도시인 경우
d[c][v] = Math.min(d[c][v], tsp(i, (v | (1 << i))) + W[c][i]);
}
}
return d[c][v];
}
}문제
시간초과를 받았다.
다양한 블로그 코드도 돌려보고 질문게시판도 찾아본 결과 다양한 사람들이 시간초과문제를 겪고있으며, 1년전 코드도 시간초과가 뜨고 해결되지않은 케이스가 많은걸로 보인다.
원인
해결
https://chb2005.tistory.com/86
위 링크를 참고하여 해결했다,,
특히 3-1. 주의사항 (시간초과 해결방법)에서 큰 도움을 받았다.
- 모든 도시 방문 후 마지막에 시작도시로 갈 수 없는 경우(cannotCycle)와 방문하지 않은 경우(notVisit)를 분리시켜야 함
- 갈 수 없는 경우에 notVisit을 return 시킨다면 나중에 방문하지 않은 상황으로 판단하여 다시 방문하는 상황 발생 => 시간초과
- cannotCycle의 값은 입력 데이터로 만들어질 수 없을 정도로 큰 값으로 임의 지정
- cannotCycle이 notVisit보다 작아야 함 => cannotCycle이 더 크면 dist에 갱신이 안되기 때문
- notVisit을 int 최대값으로 하면 실행 중 int의 최댓값 넘어가는 상황 발생하기 때문에 cannotCycle보다 더 큰 임의 값으로 지정
import java.util.Arrays;
import java.util.Scanner;
public class p2098 {
static final int cannotCycle = 17 * 1000000 + 1;
static final int notVisit = cannotCycle * 2;
static int n;
static int[][] in, dist;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
in = new int[n][n];
dist = new int[n][ 1 << n ];
for(int i = 0 ; i < n ; i ++) {
for(int j = 0 ; j < n ; j ++) {
// 0이면 갈 수 없음을 의미
in[i][j] = sc.nextInt();
}
// dist 배열 초기화
Arrays.fill(dist[i], notVisit);
}
dist[0][0] = 0;
System.out.println(tsp(0, 0));
}
static int tsp(int now, int visited) {
// 현재 노드 방문 처리
visited = visited | (1<<now);
// 모든 노드를 방문한 경우
if(visited == (1<<n) - 1) {
// 마지막 노드(now)에서 처음으로 갈 수 없는 경우
if(in[now][0] == 0) {
return cannotCycle;
}
// 갈 수 있는 경우 : 마지막 노드(now)에서 0으로 가는 비용 return
return in[now][0];
}
// 전에 최소경로를 구해놓은 경우 : 구해놓은 최소값 return
if(dist[now][visited] != notVisit) {
return dist[now][visited];
}
for(int next = 0 ; next < n ; next ++) {
// now에서 next로 갈 수 있는 경우
if(in[now][next] != 0) {
// 아직 next를 방문하지 않은 경우
if( ( visited & (1<<next) ) == 0) {
// visited에 해당하는 노드들을 방문하고 현재 now에 있는 상황
// 이 상황에서 남은 노드들을 방문하는 최소값이
// now에서 next로 간 후 next에서 남은 노드들을 방문하는 최소값보다 크다면 갱신 필요
int temp = tsp(next, visited) + in[now][next];
if(dist[now][visited] > temp) {
dist[now][visited] = temp;
}
}
}
}
return dist[now][visited];
}
}그런데 이 코드를 보고도 이해되지않는 부분이 있다.
의문점
- 방문할 수 없어서 아예 cannotCycle을 의미하는 엄청 큰 값이 출력되면 그것또한 답이라고 인지하고 통과되는건가?
공부한 사항
// 아직 next를 방문하지 않은 경우
if( ( visited & (1<<next) ) == 0) 라는 코드가 있는데, 저런 식을 쓰면 해당 노드만 체크가 가능한건가? 처음에 조금 이해되지않았다.
예를 들어 visited = 1010(2) 라서 1,3번 노드를 방문한 상태이고 next는 2라서 100(2) 2번노드를 확인하는 경우라면 &의 결과가 '0000'이 된다. 즉, visited에 어느 노드가 1이든 0또는 1의 결과를 리턴하며 검사한다.
