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

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

2098번: 외판원 순회

 

안녕하세요.

 

처음에는 다익스트라? 했는데 사이클 그래프가 생기기 때문에 취소.

 

다시 보니 DP와 DFS를 사용하는거 같더라구요.

 

DFS는

1) 한 번 방문한 도시는 다시 방문할 수 없고,

2) 어느 도시를 들려야 최소 비용이 될 지 판단해야하기 때문에,

3) N이 16 이하인 경우이기 때문에

 

사용했고, 

3)의 경우에 좀 더 효율적으로 시간과 메모리를 줄이기 위해 

DP를 사용해야 했습니다.

(저는 여기서 막혀서 다른 분들의 해설을 참고했었습니다..)

 

찾아보니 

TSP(외판원 순회) 라는 알고리즘으로 이름이 정해진 것 같더라구요.

 

DP와 비트마스크를 이용해서 해결하는 문제였습니다.

 

 

이에 대한 설명은 제가 여기 기재하는 내용보다 다른 분들이 작성해주신 내용들이 더욱 이해가 쉽고 도움이 될 것 같아서 제가 본 링크 몇 개 첨부하겠습니다.

 

https://withhamit.tistory.com/246
https://red-pulse.tistory.com/29

 

 

 

매커니즘

---

* 위의 링크를 보고 난 후 읽어주시면 감사하겠습니다!

 

dp[i][j] = 현재 있는 도시가 i이고 이미 방문한 도시들의 집합이 j일때, 방문하지 않은 나머지 도시들을 모두 방문한 뒤 출발 도시로 돌아올 때 드는 최소 비용.
즉, 방문해야하는 도시(여기에 시작지점으로 돌아오는 것 포함) 들까지 가는 최소 비용

 

여기서

N = 5(도시가 5개) 일 때

i 의 범위는 0 <= i < 5 이고, j의 범위는 00000(2) <= j <= 11111(2) 가 됩니다.

   *** (2)는 2진수를 뜻합니다.

 

예를 들어,

오른쪽부터 시작해서 i번째 도시라고 읽을 때

 

6(10) = 00110(2) = 2번째, 3번째 도시를 방문한 경우 

31(10) = 11111(2) = 1, 2, 3, 4, 5 번째 도시 모두 방문한 경우

1(10) = 00001(2) = 1번째 도시 모두 방문한 경우

 

가 됩니다.

 

 

즉, 방문한 도시를 나타내기 위해 2진수로 표현하고, 이를 비트마스크를 통해 저희는 10진수로 사용하는 것입니다.

 

 

 

 

다음,

 

DFS 알고리즘을 통해 DP의 값(모든 도시를 순환하는데 드는 최소 비용)을 찾아내야 하는데,

DP는 어떻게 정의를 내려야 할까요?

 

 

(withhamit 님의 게시글 그림을 참고했습니다.)

 

 

여기서 보면, 5번 도시까지 가는 경로는 

 

1 - 2 - 3 - 5

1 - 3 - 2 - 5

 

가 있다고 가정했을때,

 

남은 도시들을 방문하고 1번으로 돌아가는 비용은 어떻게될까요?

그렇습니다.

5 -> 4 -> 1

한 가지 경우밖에 없지요?

 

모든 경로에 대해 계산할 때, 저렇게 남은 경로의 비용을 일일히 구할 필요가 없습니다.

왜냐하면, 남은 경로의 최소비용은 남은 도시들과 목적지가 같다면 어차피 계산했을 때, 같은 비용이 나오기 때문이지요!

 

이를 DP로 저장해놓고, 사용하는 겁니다.

 

 

마지막으로,

그럼 1~N번 도시 모두 시작점으로 놓고 한 번씩 최소비용을 찾아봐야 하느냐?

 

이거에 대한 해답은 NO! 입니다.

 

 

실제 알고리즘을 작성한 후, 하나씩 대입하면 최소비용은 일정합니다.

이유는 바로 어느 도시에서 출발하든 순회 하기 때문에, 결국 경로가 일정하다는 것입니다.

 

백준 알고리즘 질문 게시판 중 일부

백준 알고리즘 질문 게시판 중 일부

ex)

1 - 2 - 3 - 4 - 5 - 6 이 최소비용일 때,

2 - 3 - 4 - 5 - 6 - 1 또한 최소비용일 테고(위에서 2 ~ 6 경로가 최소비용이기 때문에 따라간다)

3 - 4 - 5 - 6 - 1 - 2 또한 최소비용일 테고(위에서 3 ~ 1 경로가 최소비용이기 때문에 따라간다)

4 - 5 - 6 - 1 - 2 - 3 또한 최소비용일 테고 

...

 

이렇게 결국 최단경로의 사이클이 이뤄지기 때문입니다.

 

 

 

 

정리하자면

---

dp[i][j] = 현재 있는 도시가 i이고 이미 방문한 도시들의 집합이 j일때, 방문하지 않은 나머지 도시들을 모두 방문한 뒤 출발 도시로 돌아올 때 드는 최소 비용.

 

1) DP를 사용

2) 방문한 도시를 나타내기 위해 2진수 비트마스크 활용(코드 상에선 10진수로 사용)

3) DP를 구하기 위해, 최소 비용의 경로를 구하기 위해 DFS 알고리즘 사용

4) 최단경로의 사이클이 만들어지고, 최단 경로는 동일하기 때문에 1개의 도시를 시작점으로 해서 경로를 구해도 된다.

 

을 기억하시면 됩니다.

 

 

 

감사합니다!

 

 

 

 

소스코드

---