[BOJ] 백준 10971번 - 외판원 순회 2(with Java)

문제

알고리즘

1. 한 노드에서 다른 노드로 이동하는데 필요한 비용 데이터를 저장하기 위해서 인접리스트를 선언하고 값을 저장한다.

2. 최소 비용을 구하기 위해서 편의상 answer를 최대값으로 초기화 및 출발 지점 i를 방문처리하고 DFS를 시작한다.

3. DFS 메소드에서 매개변수 start와 인접한 각각의 노드까지의 이동 비용이 0이 아니고 방문하지 않았는지 확인한다.

4. 조건을 모두 만족하면 인접 노드 adj.idx를 방문처리 후에 i에서 출발하고 다시 돌아올 때까지 필요한 비용 sum에 인접 노드까지의 비용 adj.cost를 더해준다.

5. DFS를 수행할 때마다 start와 sum을 갱신하고 메소드를 빠져나올 때 다음 경우의 수를 확인하기 위해서 백트래킹을 수행한다.

6. target 노드를 제외한 나머지 노드가 모두 방문됐다면 마지막 노드에서 target 노드로 돌아올 수 있는지 확인하고 필요한 비용을 sum에 더해서 값을 갱신한다.

7. 정답 출력을 위한 answer와 sum을 비교해서 sum의 값이 더 작으면 answer를 갱신하고 메소드를 빠져나온다.

8. 모든 노드에 대해서 외판원 순회를 진행한 후에 최종적으로 도출된 answer 값을 출력한다.

소스코드

문제링크

10971번: 외판원 순회 2