백준 10971. 외판원 순회 2

문제

모든 도시를 방문하고 다시 현재로 돌아오는 데 걸리는 최소 비용을 구해라

[입력]

첫 줄에는 방문해야할 도시의 수를 입력받는다.

그 다음에 도시 사이를 이동하는 비용을 배열로 받는데, cities[i][j]란 i -> j 도시로 이동하는 데 드는 비용을 의미한다.

[정리]

• 모든 도시를 거쳐야 한다.
• 한번 거쳤던 도시는 재방문할 수 없다.
• 마지막 도시를 거친 후 처음 도시로 돌아가야하는 데, 걸리는 최소 비용을 구한다.

문제 풀이

도시의 수(N)가 10개 이하이다. 모든 도시를 방문했을 때도 10! 이기 때문에 1초안에 실행이 가능하다.

따라서 백트래킹을 구현하였다.

 

⭐ key point!
if value > ans 로 만약 모든 도시를 방문하지 않더라도 이미 결과 저장 값(ans) 보다 크다면 즉시 리턴을 통해 시간을 더 줄일 수 있었다.