백준 - 외판원 순회2

문제 출처: www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

백트래킹을 이용해서 순회를 완료하면 이전 노드로 돌아가서 다시 새로운 경로를 찾아서 최소의 비용을 도출하는 것이 관건인 문제다.

 

백트래킹을 편리하게 하기 위해 우선 입력 값들을 ArrayList배열에 넣어서 사용하였다. 여기서 문제가 발생했는데 뒤에 풀이를 하면서 언급하겠다.

 

ArrayList배열에 다음 이동점의 노드 번호, 다음 노드와의 비용 값을 넣기 위해 Point클래스를 만들었다.  그리고 이중 for문을 이용하여 입력값을 받았다.

 

 

리스트에 입력값 넣기

 

그리곤 각 노드마다 DFS를 통해 최소 비용을 찾았다! DFS코드에 들어가기 전에 우선 방문 체크를 해주었고(boolean형 배열을 사용)

해당 노드에서 시작한 DFS가 끝나면 방문을 풀어주었다.

 

 

 

 

 

DFS로직은 매우 간단하다. 방문한 배열은 다시 방문해서는 안되지만, 처음 시작 노드는 다시 방문해야 하므로 총 노드 개수가 N개일 경우, N-1 노드까지 왔으면(매번 DFS를 통해 다음 노드로 이동할 때마다 count+1을 해주었다.) 처음 시작 노드가 방문 가능한지 확인하였고, 방문이 가능하면 최소 비용을 계산하였다.

 

 

 

 

여기서!! 위에서 말한 문제점에 대해 말하겠다. 문제점이라기 보다는 내 부주의(?)로 발생한 문제였다. 초반에 리스트에 값을 입력할 때 0이면 아예 입력을 못하게 했는데 그렇게 하면 안 된다. 그러면 갈 수 있는 노드인지 못 가는 노드인지 판별이 불가능하다.

 

 

전체 코드