[백준] No.2098 - 외판원 순회 (C++, 비트마스크)

문제

 

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

2098번: 외판원 순회

 

 

풀이

 

solved.ac 난이도: Gold 1

 

 

단순히 다이나믹 프로그래밍을 적용하기에는 방문한 도시의 조합이 구현하기 힘들다.

총 도시의 개수가 16 이하이므로 비트마스크를 이용하여 방문한 도시는 bit 1, 아직 방문하지 않은 도시는 bit 0으로 표시하여 구해주자.

 

now_city은 지금 위치한 도시

visited 는 방문한 도시의 비트 표현과

cache[now_city][visited] 를 이용하여 방문하지 않은 도시들을 방문하면서 시작 도시로 돌아가는 최솟값을 구해보자.

 

처음에는 cache[시작 도시][now_city][visited]인 3차원 배열로 문제를 해결하였다.

5가지 도시가 있고 도시 0,1,2들을 먼저 방문하고 도시 3을 방문한 후 마지막으로 도시 4를 방문할 경우 가능한 경로를 생각해보자.

 

도시 0에서 시작해서 마지막에 도시 4로, 도시 1에서 시작해서 마지막에 도시 4로, 도시 2에서 시작해서 마지막에 도시 4로가는 3가지 경로가있다.

마지막 도시인 도시 4에서는 도시 0, 1, 2로 가는 각각의 비용이 다를 수도 있고 도시 4에서부터 시작 도시로 가는 길이 없을 수 도 있다. 따라서 2차원 배열로는 시작 도시마다 달라지는 도시 순회의 최솟값을 구현할 수 없다고 생각했다.

 

일단 시작 도시만 다르고 경로는 같은 두 가지 경우를 생각해보자.

1번 경로(0에서 시작): 0-> 1-> 2-> 3-> 4-> 0

2번 경로(2에서 시작): 2-> 3-> 4-> 0-> 1-> 2

 

어느 도시에서 시작하더라도 결국 도시 i에서 도시 j로 가는 비용w[i][j]의 합은

w[0][1] + w[1][2] + w[2][3] + w[3][4] + w[4][0]로 같다.

즉, 어느 도시에서 시작하든 경로의 비용은 같기 때문에 임의의 도시에서 시작한 값만 구해줘도 모든 도시에서 시작한 최솟값을 구한 것과 같다.

 

그렇다면 위의 가정처럼 도시 3을 방문하고 도시 4를 방문하는 경우를 생각해보자.

1번 경로(0에서 시작): 0-> 1-> 2-> 3-> 4-> 0

2번 경로(1에서 시작): 1-> 0-> 2-> 3-> 4-> 1

3번 경로(2에서 시작): 2-> 1-> 0-> 3-> 4-> 2

 

앞에서 본 것처럼 어느 도시에서 시작하던 비용의 합은 같기 때문에 경로를 아래와 같이 바꿔보자.

1번 경로(0에서 시작): 0-> 1-> 2-> 3-> 4-> 0

2번 경로(0에서 시작): 0-> 2-> 3-> 4-> 1-> 0

3번 경로(0에서 시작): 0-> 3-> 4-> 2-> 1-> 0

 

이 경우는 DFS형식의 재귀함수를 구현하여 모든 경로를 방문해보면 결국 한 번씩은 계산되는 값이다.

따라서 2차원 배열 cache[now_city][visited]로도 충분히 값을 계산할 수 있다.

 

함수 int TravelCities(int now_city, int visited) DFS방식의 재귀호출로 

now_city에서 방문하지 않은 도시들을 방문해간다.

 

~visited & (1<<i) == true라면 i번째 도시는 방문하지 않은 것이므로 

현재 도시에서 해당 도시로의 길이 있다면(  travel_cost[now_city][i] !=0 )

visited | (1<<i) 로 해당 도시는 방문했다는 표현을 해주고 재귀 호출로 최솟값을 구해간다.

 

cache[now_city][visited] = min(cache[now_city][visited] ,

TravelCities( i, visited |(1<<i)) + travel_cost[now_city][i]);

 

기저사례는 모든 도시를 방문한 경우이다.

만약 마지막으로 방문한 도시에서 시작 도시(임의의 도시로 설정, 코드에서는 0으로)로 돌아가는 길이 없다면

즉, travel_cost[now_city][0]가 0이라면 MAXN값을 반환한다.

돌아가는 길이있다면 travel_cost[now_city][0]를 그대로 반환해준다.

 

2차원 배열과 3차원 배열로 각각 해당 문제를 풀었을 때의 실행 속도 비교는 아래와 같다.

 

코드