[Leetcode] 847. Shortest Path Visiting All Nodes

 

문제 : https://leetcode.com/problems/shortest-path-visiting-all-nodes/description/

 

 

---

우선 플로이드 워셜 알고리즘으로 모든 정점간 최단거리(dist)를 구한다.

구한 dist 배열로 플로이드 워셜 알고리즘이랑 비슷하게 정답을 구한다.

기본 알고리즘은 다음과 같다.

 

 

여기서 상태란 node들이 포함된 상태를 의미한다. (참고)

즉, 플로이드 워셜 알고리즘 처럼 3중 for문을 돌린다.

중간 지점을 중간에 거치는 상태로 두고 시작 노드에서 종료 노드로 갈 때 거치는 최소 간선의 수를 구한다.

조건문에 시작노드가 포함되고 종료노드는 포함되지 않은 상태가 중간상태가 되야 하는 이유는

중간상태에 시작노드가 있어야만 시작 상태가 될 수 있고,

중간상태에 종료노드가 있는 경우는 중간상태가 아닌 이미 우리가 원하는 경우를 포함된 상태이므로 구할 필요가 없기 때문이다.

 

위 알고리즘으로 d 배열을 모두 채우면

d[모든 노드를 포함한 상태][0~노드 수] 에서 가장 작은 경우가 정답이 된다.

---

 

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/847.%20Shortest%20Path%20Visiting%20All%20Nodes.cpp

 

---

토론글 참고해서 해결했다. 다 구현하고 보니까 너무 비슷하게 짰더라;; 나도 모르게 따라가고 있었나보다. 참고 토론글

 

처음에는 플로이드 알고리즘 써서 각 정점간 최단거리 구한다음에 TSP 알고리즘을 도입하려고 했었다. 그런데 구현하다 보니까 플로이드 필요없어서 빼고 구현했는데 일부 TC에서 fail이 떠서 완성은 못했다. 원인이 뭔지 아직 잘.. 몰겠다. 더 생각해봐야겠다. (소스코드)

이전에는 문제 잘 못 이해해서 연결되어 있는 노드의 최대 개수를 구하는 건 줄 알고 쉽구먼 하고 Union FInd 써서 구현했는데 문제가 이게 아니었다. (소스코드)