koko514   2년 전

외판원 순회 알고리즘이 궁금하여 찾아보았습니다.

답에 가장 관련있는 부분은 지웠구요..

궁금한 것은 문제는 어느 한 도시에서 출발하여 다시 그 도시에 도착하는데에 최소 비용을 요구하는데 이 코드는 0 도시에서 시작하여 0 도시로 오는데의 최솟값을 구한거 아닌가요? 

정답자 코드 보았는데 대부분 cur이 0에서 시작하여 다 방문하면 city[cur][0]을 return하던데 이것이 어떻게 최솟값이 될 수 있는지가 궁금합니다.

onjo0127   2년 전

외판원이 모든 도시를 정확히 한 번씩 방문한다는 점을 잘 생각해보면, 어느 도시에서 출발했던 간에 항상 같은 답이 나온다는 걸 알 수 있습니다.

koko514   2년 전

죄송합니다만 1번부터 5번까지 노드가 5개 있다고 치면, 1 - 2 - 3 - 4 -5 - 1 와 2- 1 - 3 - 4 - 5 - 2 가 단방향 그래프니까 서로 다른값 을 가지지 않나요? 따라서 최솟값도 모든 노드에대해서 다 구해야 되는거 아닌가요? 

koko514   2년 전

해결했습니다. 감사합니다.!

sotter1020   2년 전

저도 이거 궁금한데.. 해결하셨으면 알려주시면 안될까요?

저도 처음에 모든 노드가 출발했을 경우를 생각해서 코드를 짰는데..

메모제이션 크기에서 문제가 생겨 고생좀 했다가 이 관점에서 보고 풀었는데 맞긴했거든요..

근데 왜 어느 정점에서 출발하든 최소값이 나오는지 잘 모르겠습니다..

댓글을 작성하려면 로그인해야 합니다.