[정올] 1681번. 해밀턴 순환회로 (java, MST)
Posted by 해랑쓰 블로그 (Haerang's blog)
시작지점으로 돌아가는 최소 거리를 찾아야 하므로 모든 경우를 살펴봐야되서 dfs + 백트래킹으로 풀면된다. 모든 지점을 모두 방문할 수 있는 경우는 많은데 그 중 시작지점인 1로 돌아올 수 있고 이미 구했던 답보다 새로 구한 전체 방문 거리가 더 작다면 갱신해준다. 중간에 구한 거리가 이미 구한 거리를 넘어가는 순간도 return처리를 해줘서 시간 초과를 막아줘야한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static int n; stat..