외판원 순회 문제란?
어떠한 도시에서 출발하여 다른 모든 도시들을 거쳐 출발 했던 도시로 다시 돌아오는데 드는 최소 비용을 찾는 문제이다.
외판원 순회 문제의 경우 도시(N)의 개수가 10개 이하일때와 16이하일때 2가지로 나눠서 생각 할 수있다.
(시간복잡도 문제로 해결방법이 다르다.)
N <= 10 인 경우
10개 이하의 경우 완전 탐색을 통해서 구할 수 있다.
10개 도시를 돌아 다시 돌아오는 경우는 10! = 3628800으로 계산할 수있다.
즉, 완전 탐색을 통해 해결할 수있다.
여기서 살펴볼 사항이 몇 가지 있다.
첫 번째, 시작 지점을 A도시로 고정 시킬 수 있다.
시작지점을 어디를 잡아도 순환이기때문에 같은 경로가 되기 때문이다.
-> 이를 통해 반복문 하나 정도는 줄여줄 수 있다.
두 번째, 중복되는 문제가 발생한다.
이 중복 계산하는 문제를 DP를 이용하여 해결하면 16개 까지의 도시를 해결 할 수 있다.
N <= 16 인 경우
DP 적용 방식
dp[현재 도시][방문한 도시] = 나머지 도시들을 방문하는데 드는 최소비용
이를 통해서 N<=10일때 발생한 문제,
현재도시 D에서 A,B,C를 방문한 상태에서 나머지 도시들을 방문하는데 드는
최소 비용을 저장하여 중복 계산하는 과정을 해결 할 수있다.
여기서 A,B,C를 방문한 상태를 표시 하기위해서 비트마스크를 사용한다.
A,B,C,D를 방문한 경우 1111
A,B,C를 방문한 경우 1110
A,C를 방문한 경우 1010
C를 방문한 경우 0010
관련 문제 : 백준(BOJ) 2098 외판원 순회 **
'IT > 알고리즘 및 자료구조' 카테고리의 다른 글
| [알고리즘 정리] 최장 증가 수열(LIS,Largest Increasing Sequence) 알고리즘 (2) | 2018.07.16 |
|---|---|
| [알고리즘 정리] 최소 신장 트리(MST, Minumum Spanning Tree) 알고리즘(프림 알고리즘) (0) | 2018.06.03 |
| [알고리즘] 비트를 이용한 시프트, 논리 연산 ( <<, >>, &, |) (0) | 2018.06.02 |
| [알고리즘] STL lower_bound(), upper_bound(), equal_range() (0) | 2018.06.01 |
| [알고리즘 정리] CCW(Counter Clock Wise) 알고리즘 (0) | 2018.05.31 |
