[java 백준] 골드 1/ 2098번 외판원 순회 2

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

2098번: 외판원 순회

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
class Main {
 
    public static int n;
    public static int map[][]=new int[17][17];
    public static int dp[][]=new int[17][1<<16];
 
    public static int INF = (int)1e9;
    public static StringBuilder sb=new StringBuilder();
 
 
    public static int TSP(int city, int visit) {
 
        if(visit==(1<<n)-1){
            if(map[city][0]!=0){
                //시작점인 0으로 돌아갈 수 있다면
                return map[city][0];
            }
 
            return INF;
        }
 
        if(dp[city][visit]!=Integer.MAX_VALUE){
            return dp[city][visit];
        }
 
        for(int i=0;i<n;i++){
            if(map[city][i]!=0&&(visit&(1<<i))==0){
                int temp=TSP(i,visit | 1<<i);
                if(temp!=Integer.MAX_VALUE){ //만약 중간에 사이클이 끊기는경우도 생각해야함.
 
 
                    temp+=map[city][i];
                    dp[city][visit]=Math.min(dp[city][visit],temp);
 
                }
            }
        }
 
 
 
        return dp[city][visit];
    }
 
 
    public static void main(String args[]) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        n = Integer.parseInt(br.readLine());
 
        for (int i = 0; i < n; i++) {
            StringTokenizer st=new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
            for(int j=0;j<n;j++){
                Arrays.fill(dp[i],Integer.MAX_VALUE);
            }
 
        }
 
        dp[0][0]=0;
 
 
        sb.append(TSP(0,1));
        System.out.println(String.valueOf(TSP(0,1)));
 
        
    }
 
}
 
 

 

 

외판원 순회는 보통 비트마스크 + dp로 많이 푸는 것 같아서 다른 사람들의 풀이를 참고했다.

특히 비트마스크는 재귀를 이용하는데 재귀는 항상 끝에서 앞으로 가는 방식을 사용하기에 거꾸로 생각해줘야 해서 그게 좀 힘들었다.

✨중요한것은 최소 루트만 찾으면 되고, 어차피 순회하기 때문에 (다시 처음위치로 돌아와야 하기에) 시작점은 어디인지가 중요하지 않다.  예를 들어 최소루트가 0->1->2->3->0 이면 (출발지가 0일때)

0->1->2->3->0 이던 1->2->3->0->1 이던 똑같기 때문이다!!

 

 

비용을 담아주는 배열 arr과 현재 위치에서 어떤 노드들을 지나왔는지 알려주는 배열 dp를 선언한다.

dp는 dp[현재 위치][현재 위치를 기준으로 그 동안 지나온 노드] 의 형식으로 선언해주는데 여기서 비트 마스크를 이요한다.

 

예를 들어 현재 위치가 3이고 0,1,2번째 도시를 지나왔다고 해보자.

그러면 이것을 dp[3][0111] 로 나타낼 수 있다. 

도시를 지나오면 -> 1

도시를 아직 지나가지 않으면 -> 0 

이렇게 이진수를 사용해주는 걸 비트마스크라고 한다.

dp[3][0111]은 사실상 dp[3][7]과 똑같은 말이다.

 

그러면 처음에 크기를 설정해 줄 때 (1<<n)-1이라고 했는데

 

예를 들어 n이 4라면 처음에 크기를 1111로 잡아줘야 한다. 0,1,2,3번째 도시(총 4개의 도시)를 모두 지나가는게 최대이기 때문이다.

 

1111를 비트 연산을 통해 나타내면 (1<<4) -1 이다. 1<<4는 10000인데 이걸 10진수로 나타내면 16이다 여기서 1빼면 15인데 이걸 2진수로 나타내면 1111이기 때문이다. 

 

그리고 dp에 있는 모든 원소를 MAX로 채운다. 

max는 성분으로 주어질 수 있는 1,000,000보다 훨씬 큰 수를 두면 된다. 다른 사람들 코드 중에서는 987654321이 가장 많았다. 

시작 위치는 어디서 하던 상관 없다. 어차피 사이클 처럼 돌기때문에 경로가 일정하다. 그래서 나는 0을 시작점으로 두었다.

 

이제 dfs메서드를 살펴보자.  

 

 

모든 도시를 다 순회했을 때 그 지점에서 다시 처음 시작했던 도시였던 0으로 돌아가는 값을 리턴해준다.

 

여기서 부터 재귀를 쓰기에 헷갈린다.

 

dp[0][1]이면 현재 0의 위치에서 0번째 도시만 방문했으니까 값이 0일것 같은데 dp[0][1]은 35이다. 그 이유는 재귀를 쓰기에 전부다 돌았을 때 부터, 즉 끝에서 부터 처음 시작할 때 까지 반대로 계산하기 때문이다.

 

예를 들어 dp[3][1011]는 무엇일까? 지금 위치는 3이고 그동안 0,1,3번째 도시를 거쳐왔다는 것이다. 그렇기에 이것을 재귀의 관점에서 이해해보면

 

남은 도시는 2번째 도시이기에 (3번째 도시에서 2번째 도시까지 가는 비용)+(2번째 도시에서 다시 처음으로 가는 비용) = 15가 된다.

 

다른 예시도 살펴 보자. dp[1][11]은 1의 위치에서 현재 0,1번째 도시를 거쳐왔으니 2,3번째 도시를 모두 돌때까지의 비용 + 마지막 도시에서 다시 처음으로 가는 비용이라고 생각하면 된다. 

 

즉 dp[i][j]는 i의 위치에서 j의 이진수를 파악해서 남은 도시까지 돌때까지의 비용+마지막 도시에서 다시 처음으로 가는 비용 이라고 생각할 수 있다.

 

그러면 여기서 빼먹은게 하나 있는데 바로 최소값이다! 이제 최소값을 설정해주러 가보자. 

 

만약 dp에 값이 있으면 그 값을 바로 리턴해준다.

 

 

여기서 부터 최소비용을 설정해주는 코드이다.

 

if문의 조건은 한번도 방문하지 않은 경우&& 자기자신을 방문하지 않은 경우이다. 

 

자기자신을 방문하지 않는 경우의 코드는 이해가 될텐데 visit &(1<<i)는 약간 이해가 되지 않을 수 있다.

 

우리가 dfs(0,1)을 받아왔는데 이는 현재 위치는 0번째 도시이고 0번째 도시 하나만 방문한 것을 의미한다.

만약 i가 0 이면 1 & (1) 이기에 비트연산을 하면 1을 반환한다.

i가 1이면 1&(1<<1) 이기에 1&10이 되고 이럴 경우 1을 반환한다. --> 이 말은 1번째 도시로 이동할 수 있다라는 것을 의미한다. 

 

즉  visit &(1<<i)는  visit이 방문하지 않은 경우의 수를 찾아주는 것이다. 

 

dfs(i,visit | (1<<i)) +arr[node][i]의 의미를 살펴보자.

우선 i가 1일때 저 if문은 통과할 수 있다.

 

그러면 현재 위치는 0에서 1번째 도시로 이동한다.

 

visit | 1<<1은  1 | 1<<1 이고 이는 1 | 10이다. 이걸 비트 연산하면 11 이된다. 이말은 내가 0번째 도시도 지나오고, 1번째 도시도 지나왔다는 것을 의미한다. 

 

그러면 dfs(1,11) + arr[0][1] 을 해주면  0번째 도시에 1번째 도시로 정말 넘어간것이기에 그 비용인 10만큼 더해주는 것이다.

 

결론적으로 Math.min을 통해 가장 최소의 dp[0][1]값을 찾는다. 즉, 0의 위치(처음)에서 남은도시까지 도는 비용 (여기서는 0번째 도시만 지나왔으니까 남은 1,2,3번째 도시를 지나가는 비용) + 마지막 도시에서 0까지 오는 최소비용이 dp[0][1]이다.

 

---

 

 

여기서 부터는 나중에 내가 시간이 지나서 까먹었을 때 볼려고 상세하게 풀이과정을 적어놓을거다. (재귀는 항상 헷갈려서 이렇게 쓰면서 적어야 이해를 할 수 있다..)

 

dfs(0,1)일때 

 

visit값은 1이기에 그 다음에 지나갈 수 있는 도시의 경우의 수는

 

1번) 1<<1 이기에  이진수로 10 , 1번째 도시 

 

2번) 1<<2이기에 이진수로 100 , 2번째 도시

 

3번) 1<<3이기에 1000, 3번째 도시 

 

1번 경우의 수 부터  보면

 

dp[0][1]= Math.min(max,dfs(1, 1 | (1<<1) +arr[0][1]) 이다.

 

dfs(1,1 | (1<<1)은 결국 dfs(1,11)이다. 즉, 현재 1의 위치인데 0번째,1번째 도시 다 돌았다는 말

---

dfs(1,11)은 

 

경우의 수가 또 2가지로 쪼개진다.

 

1번) 1<<2 이기에 이진수로 100 -> 2번째 도시로 가는 경우

 

dp[1][11]=Math.min(max,dfs(2, 11 | (1<<2) +arr[1][2]) 

 

여기서 dfs(2, 11 | 100) 은 dfs(2,111) 즉 현재 위치가 2이고 0,1,2번째 도시를 지나왔다는 것  

 

2번) 1<<3 이기에 이진수로 1000 -> 3번째 도시로 가는 경우

 

dp[1][11]= Math.min(max,dfs(3, 11 | (1<<3) + arr[1][3])

 

여기서 dfs (3,1011)은 현재 위치가 3이고 0,1,3번째 도시를 지나왔다는 것이다. 

 

---

dfs(2,111) 과 dfs(3,1011)을 보자

 

dfs(2,111)은 

 

1<<3 ,이진수로 1000 -> 즉 3번째 도시로 가는 경우만 남았다. 

 

dfs(3, 111 | 1000)을 하면 dfs(3,1111)이 되면서 모든 도시를 다 돌았기에 arr[3][0]이 반환된다.

 

 

dfs(3,1011)은 2번째 도시로 가는 경우만 남았다.

 

dfs(2,1011 | 100)을 하면 dfs(2,1111)이 되면서 arr[2][0]이 반환된다.

 

 

이제 끝에서부터 처음으로 다시 돌아가면 

지금까지는 0번째 -> 1번째만 가는 경우만 생각해봤지만 0번째 -> 2번째 / 0번째 ->3번째 경우도 존재한다.

 

다만 0번째 -> 1번째가 가장 최소인 35를 가지기에 0번째 -> 1번째만 해 본 것이다. 

 

 

참고 사이트

https://maivve.tistory.com/306

(JAVA) 백준 2098번 : 외판원 순회 --- [DP, TSP, 비트마스크]

 

 

비트 마스크 

https://mygumi.tistory.com/361

비트마스크(BitMask) 는 무엇인가? :: 마이구미

 

 

시간복잡도를 줄이기 위해서

 

https://chb2005.tistory.com/86

[JAVA] 외판원 순회 문제 (TSP) + 시간초과 해결방법

처음 방문한 곳을 Integer.MAX_VALUE로 사이클이 되지않으면 INF를 반환하면 된다. 

 

특히 중요한게 이부분인데 temp != Integer.MAX_VALUE를 해줘야 중간에 만약 사이클이 끊긴 경우인 경우 가차 없이 끝낼 수 있다. (분명 사이클이 끊기면 옆으로 갈 수 있는 노드도 없어서 DP에 넣어준 기본값인 Integer.MAX_VALUE가 반환될 것이다!)