Back-Tracking1 [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 노드를.. 2022. 6. 30. 이전 1 다음
