java
-
[백준]10971. 외판원 순회2알고리즘/백준 2020. 12. 21. 23:39
📄 링크 외판원 순회2 💡 문제 분석 알고리즘의 대표적인 문제입니다. 모든 도시를 방문하고 시작 지점으로 돌아 오는데 필요한 최소 비용을 구하는 문제입니다. 완전 탐색으로 모든 경로를 계산해서 최소 비용을 구하는 방법을 사용할 수 있지만, 이럴 경우 O(N!)의 시간 복잡도가 소요됩니다. 이 문제에서는 N의 최대값이 10이기 때문에 10! = 3628800으로 시간 초과가 나지 않지만, N이 12를 넘어가게 되면 약 5억으로 시간 초과가 날 것입니다. 그렇기 때문에 부분문제로 쪼개서 동적 계획법을 사용하기로 했습니다. tcp(cur, visited) = 현재 방문한 도시들이 visited이고 현재 위치가 cur일 때 모든 도시를 방문하고 시작 지점으로 돌아가는데 필요한 최소 비용 이렇게 최적 부분 구조로..