[백준] 2098 - 외판원 순회 (G1)
·
알고리즘 (PS)/BOJ
전에 풀었던 문제인데 2달전 재채점 때 틀려서 다시 풀어보았다. 다시 풀려니까 도저히 풀리질 않아서 외판원 순회 아이디어를 읽었는데도 모르겠었다. 그래서 결국 내가 전에 티스토리에 썼던 글을 보았는데, 신기하게 그걸 보니까 작성할 수 있었다. 나는 내가 제일 잘 아는건가ㅋㅋ 하지만 그 글에서 헷갈렸던 부분이 있어서 다시 정리하려고 한다. 1. 외판원 순회는 어디에서 시작해도 값이 같다. "도시" 가 아니라 "간선" 을 기준으로 보면 바로 이해된다. 1-3-2-1 이 최적해라고 하자. 그럼 최적해를 구성하는 간선은 1-3 3-2 2-1 이렇게 3개이다. 만약 3에서 시작했다고 하면 최적해는 3-2-1-3 이렇게 된다. 최적해의 구성 간선은 3-2 2-1 1-3 순서만 다르지 아까와 똑같다. 따라서 어디에서..