[백준 2098] 외판원 순회 -JAVA //le_effort

외판원 순회

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	18084	4532	2682	27.598%

문제

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

항상 순회할 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

예제 입력 1 복사

xxxxxxxxxx
4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0

예제 출력 1 복사

35

 

풀이

비트마스킹을 연습하려고 비트마스킹 문제들을 풀어 보고 있는데

정말 어렵게 풀었다 너무 어렵다ㅠㅠㅠㅠ

풀이까지 도움을 주신 rdd6584님께 무한한 감사를 올립니다...

 

우선 문제를 풀기 전 이해를 해야 할 게 있다.

문제에서 원하는 건 n개의 도시중 1~n 까지의 도시 중 어느 한 곳에서 출발해서 출발 한 곳으로 돌아왔을 때의 최소거리를 구해야 한다.

 

도시가 3개 있다고 쳤을 때 dfs 로

1번 도시에서 출발 했을 때 dfs

2번 도시에서 출발 했을 때 dfs

3번 도시에서 출발 했을 때 dfs

이렇게 각각의 도시마다 출발도시로 두고 각 도시마다 최소값을 비교해서 풀어야 하는 줄 알았다.

 

하지만 그렇지 않다. n개의 도시중 아무 도시나 잡고 dfs를 돌려도 값은 똑같다.

이게 왜 이렇게 될 까? 다음의 사진을 보자.

 

 

도시간의 거리는 내가 그냥 생각나는대로 아무 숫자나 적었다 절대 계산하고 적은게 아니다.

이걸 증명하기 위해 각각의 도시를 출발점으로 잡고 최솟값을 구해보겠다

1번 도시에서 출발 할 때

1->2->3->1 일 때 거리는 5+2+10 = 17

1->3->2->1 일 때 거리는 9+7+4 = 20

 

2번 도시에서 출발 할 때

2->1->3->2 일 때 거리는 4+9+7 = 20

2->3->1->2 일 때 거리는 2+10+5 = 17

 

3번 도시에서 출발 할 때

3->1->2->3 일 때 거리는 10+5+2 = 17

3->2->1->3 일 때 거리는 7+4+9 = 20

 

각각의 도시에서 최솟값이 똑같은 걸 볼 수 있다.

좀 더 자세히 이해하고 싶다면 직접 그림을 그려보고 최솟값에 해당하는 부분을 빨간색으로 칠해보면 길이 똑같다는걸 알 수 있을 것이다.

 

각 도시의 최솟값은 아래와 같다.

1->2->3->1

2->3->1->2

3->1->2->3

제일 처음 1번 도시를 기준으로 구역을 나눠보겠다

1->2 = A

2->3 = B

3->1 C

 

그럼 2번 도시를 보자

2->3->1->2 를 위에서 구했던 것과 바꾸면

B->C->A 로 완벽히 표현 할 수 있다.

 

'모든 도시를 다 순회하고' 자신의 출발도시 까지 돌아와야 하니까 어느 도시에서 출발 하건 최솟값은 같다.

 

메인함수 부분

public class Main {
    static int n;
    static int dist[][];
    static int max = 16000001;
    static int ans = 0;
    static int dp[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ans = max;
        n = Integer.parseInt(br.readLine());
        dist = new int[n][n];
        
        dp = new int[n][(1<<n)];
        for(int i=0; i<n; i++) {
            Arrays.fill(dp[i],max);
        }
        for(int i=0; i<n; i++) {
            String [] tt = br.readLine().split(" ");
            for(int j=0; j<n; j++) {
                dist[i][j] = Integer.parseInt(tt[j]);
            }
        }

코드 순서대로 내려와보자.

static 부분에서 눈여겨 볼만한건 max 랑 dp[] [] 이것이다

max는 Integer.MAXVALUE 대신 쓰인건데 이에 대한 건 밑에서 설명하겠다.

dp는 2차원 배열이다

dp [현재도시위치] [방문조합] 이렇게 사용 할 건데

우선 방문조합 이란게 뭐냐면 여태까지 방문한 도시를 비트마스킹으로 표현 할 것이다.

만약 도시가 0번도시 1번도시 2번도시 이렇게 3개 있을 떄 비트마스킹을 이용하면

000 -> 아무것도 방문x

001 -> 0번도시 방문

010 -> 1번도시 방문

100 -> 2번도시 방문

011 -> 1,2번 도시 방문

 

이런식으로 방문에 대한 정보를 저장하겠다

실제로 비트마스킹을 쓰지 않고 이를 저장하려면 어떻게 해야할까? 난 모르겠다.

 

대망의 dfs함수

xxxxxxxxxx
dfs(0,1);
System.out.println(dp[0][1]);
​
public static int dfs(int node, int num) {
        if(num == (1<<n)-1) {
            if(dist[node][0]==0) {
                return max;
            }
            return dist[node][0];
        }
        
        if(dp[node][num] != max) {
            return dp[node][num];
        }
        
        for(int i=0; i<n; i++) {
            int next = num | (1<<i);
            if(dist[node][i]==0 ||( num &(1<<i)) !=0) {
                continue;
            }
            dp[node][num] = Math.min(dp[node][num], dfs(i,next) + dist[node][i]);
        }
        return dp[node][num];
    }

 

dfs의 시작은 0번 도시에서 시작하고 dfs의 인자는 (0,1)이다

왜 0번도시에서 시작했는지에 대한 설명은 위에서 충분히 했다고 생각한다.

어떤 도시에서 시작하던지 최솟값은 같게 나온다.

그리고 dfs의 매개변수가 2개있는데 (int node, int num)

node 는 현재도시의 위치이고 num 은 방문정보에 대한 비트마스킹에 쓰일 번호이다

 

그럼 시작 할 때 왜 (0,1)을 인자로 주었을까?

나는 0번도시부터 시작한다고 정했고 그러면 0번 도시는 이미 무조건 방문 한 셈이다

아까 위에서 말했던 0번 도시를 방문했다고 표현하면 비트로 어떻게 표현할까?

만약 도시가 3개면 001 로 표현 할 수 있다.

 

001(2진수)를 10진수로 표현하면 1x2^0 = 1이다

그래서 시작부터 10진수 1을 num 에 넣어주었다 (num은 진행하면서 계속 비트마스킹에 쓰일 10진수이다)

 

 

for(int i=0; i<n; i++) {
            int next = num | (1<<i);
            if(dist[node][i]==0 ||( num &(1<<i)) !=0) {
                continue;
            }
            dp[node][num] = Math.min(dp[node][num], dfs(i,next) + dist[node][i]);
        }

이 부분을 보면 next는 num을 기준으로 (현재 방문정보) i번째 도시를 방문 한 걸로 비트 연산을 해주었다

 

즉 현재 num = 1이므로

2진수로 하면 01

1번 도시를 방문한다고 쳤을 떄

01 | (1<<1) 을 하면

01 | 10 = 11

2진수로 하면 11이고 10진수로 하면 3이다. (next 값에 들어있는건 int형이니 3)

 

그리고 밑의 if문은 dist[node] [i] 는 갈 수 없는 도시는 빼주는 거고

num & (1<<i) != 0 이 부분에 대해서 알아보자

만약 0번도시와 1번도시 까지 방문한 상태라고 치면

2진수로 011 이다

이 상태에서 우리가 방문해야 하는 곳은 2번도시이지 이미 방문한 0번도시와 1번도시가 아니다

 

0번 도시일 경우 011 & (1<<0) = 011 & 01

이걸 and연산하면 001 이라는 값이 나오면서 1라는 값이 나온다.

즉 0이 아니므로 이미 방문했다고 친다.

 

1번 도시도 마찬가지이다 011 & (1<<1) = 011 & 10

이걸 and 연산하면 010 값이 나오고 2가 나온다.

 

그럼 아직 방문하지 않은 2번도시의 경우 and연산을 진행하면 어떻게 될 까?

011 & (1<<2) = 011 & 100

이걸 and 연산하면 000 으로 0이 나온다 즉 아직 방문하지 않았다는 것이다

 

이걸 조금만 더 생각해보면

현재 011 기준으로 2번 도시만 방문 안했으니까 방문 안한곳을 and 연산하면

0이 나온다는 걸 알 수 있다.

이미 방문한 곳은 그 위치에 1이 채워져 있으니 0이 안나오게 된다.

 

그리고 dp[node] [num] = Math.min (dp[node] [num] , dfs(i,next) + dist[node] [i])

이 부분에 대해서 파해쳐보자.

 

다이나믹 프로그래밍이란 큰 문제를 해결 하기 위해서 작은 문제로 나눠 푸는 것이다

dp[0] [1] = Math.min(dp[0] [1], dfs(1,11) + dist[0] [1]) 인데

우선 Math.min에 dp[0] [1] 이 있는 것은

반복문이 i=0; i<n 까지 도는데

0번 도시기준으로 1번도시를 방문 한 것과 2번 도시를 방문한 것중 최솟값을 얻기 위해서 넣는 것이다.

 

이것에 대한 이해는 직접 작은 테스트케이스 3개 정도 (위의 내가 만든 예시를 써도 좋다)

직접 손으로 재귀함수의 흐름을 그려보는걸 추천한다

 

그리고 여기서 Integer.MAXVALUE를 하지 않고 max 값을 따로 세팅해준 이유가 나온다

dfs(i,next) + dist[node] [i]

dfs(i,next)를 한 값이 가는 길이 없어서 Integer.MAXVALUE가 나온다면

Integer.Maxvalue + dist[node] [i] 인 셈인데 이는 오버 플로우가 발생한다

 

 

if(dp[node][num] != max) {
            return dp[node][num];
        }

이 부분은 중복을 방지하기 위해서 넣었다. n의 숫자가 커질수록 이런 메모제이션 기법을 이용해서 가지치기를 해주는게 중요하다

맨 처음에 dp의 값을 max로 채워 주었기 때문에

max가 아니라는건 기존에 이미 계산이 됐다는 뜻

이건 가지치기를 해주면 된다.

 

 

if(num == (1<<n)-1) {
            if(dist[node][0]==0) {
                return max;
            }
            return dist[node][0];
        }

이 부분을 보자

num은 뭐라고 했냐면 방문한 정보(비트마스킹 2진수)를 10진수로 표현 한 것이라고 했다.

즉 if(num ==(1<<n)-1)은 모두 다 방문했다는 것이다

자 이번에도 도시(n)가 3개라고 예를 들어보자

3개의 도시를 다 방문하는걸 2진수로 표현하면 111 즉 10진수로 7이다

1<<3은 1000 이다

1은 2진수로 표현하면 뭘 까? 01 이다

비트 연산에 의해서 1000 - 01 = 111

만약 num 이 7이면 이를 2진수로 표현하면 111 이 돼서 저기 if문 분기에서 걸린다

그리고 if(dist [node] [0] == 0) return max;

이 부분에 대해서 알아보자

지금 num == (1<<n) -1 까지 왔으니 모든 도시는 다 방문 한 상태이다.

마지막으로 방문한 도시에서 시작 0번도시로 못 돌아가는건 길이 없다는 것 이니

max 값을 리턴해준다.

 

아닐 경우 현재 걸리는 거리를 return 해주면 된다.