[JO] 1681. 해밀턴 순환회로

문제

---

태현이는 방학기간 동안 택배 알바를 해서 최고급 노트북을 장만하려고 한다.

오늘 배달해야 하는 장소를 한 번씩만 방문해서 물건을 모두 배달하고 다시 회사로 돌아와야 한다.

배달하는 장소에만 도착할 수 있다면 물건은 모두 배달할 수 있으므로 물건의 개수나 크기등은 고려하지 않아도 된다.

그런데 문제는 방문하는 순서를 어떻게 정할지가 고민이다.

어떤 장소에서 다른 장소로 이동하는 데에는 비용이 발생하는데 만약 방문하는 순서를 잘못 정하게 되면

알바비로 받은 돈을 모두 이동비용으로 사용하고 눈물을 흘릴지도 모른다.

태현이가 물건을 모두 배달하고 회사로 돌아오기 위한 최소의 비용을 계산하는 프로그램을 작성해 주자.

입력형식

첫 줄은 배달해야 하는 장소의 수 N(1≤N≤13)이 주어진다. 이때, 출발지(회사)는 1번이다.

둘째 줄은 N X N 크기의 장소와 장소를 이동하는 비용(0 ≤ 비용＜ 100)이 한 칸씩의 공백으로 구분하여 주어진다.

비용은 양방향이 아니라 단방향으로 가기 위한 비용이다.

예들 들어 첫 번째 행 두 번째 열에 적힌 비용은 1번 장소에서 2번 장소로 이동하기 위한 비용을 의미하며,

2번 장소에서 1번 장소로 이동하기 위한 비용은 두 번째 행 첫 번째 열에 주어진다.

장소 사이에 이동할 수 있는 방법이 없다면 비용을 0으로 표시한다.

출력형식

회사에서 출발하여 오늘 배달해야 하는 모든 장소를 한 번씩 들러 물건을 배달하고 회사에 돌아오기 위한 최소의 비용을 출력한다.

입력 예

5
0 14 4 10 20
14 0 7 8 7
4 5 0 7 16
11 7 9 0 2
18 7 17 4 0

출력 예

30

풀이

---

문제 유형 : 백트랙킹
최단경로나 MST로 헷갈려서 kruskal 쓸지 prim 쓸지 dijkstra 쓸지 삽질했다...

1. N개의 집들 중에 회사는 처음 출발지점이므로 빼고 N-1 개의 집을 방문하는 순서를 순열을 통해 구한다.
2. 만약, 이전에 선택한 집에서 현재 집으로 올 수 없다면 (가중치가 0) 이라면 continue 한다.
3. 이전 경로의 이동비용의 합보다 현재까지의 이동비용의 합이 더 크다면 중단한다. (=가지치기, =백트랙킹)
4. N-1 개의 집을 모두 고려했다면 이동비용의 최솟값을 계산하는데, 마지막 집에서 회사로 오는 경로가 없다면 (graph[last][0] = 0) 이라면 갱신하지 않는다.
5. 최소 이동경로 비용을 출력한다.

코드

---

import java.io.*;
import java.util.*;

public class Main_jo_1681_해밀턴순환회로 {

	static int N, ans = Integer.MAX_VALUE;
	static int[][] graph;
	static int[] selected;
	static boolean[] visited;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		graph = new int[N][N];
		selected = new int[N-1];	// 출발은 0 이므로 빼고 나머지 집(N-1)을 방문하는 순서
		visited = new boolean[N];
		
		StringTokenizer st;
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<N; j++) {
				graph[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		perm(0, 0, 0);
		
		System.out.println(ans);
		br.close();
	}
	
	static void perm(int cnt, int pre, int total) {
		if(cnt==N-1) {	//n-1 개의 집을 방문했다면
			
			if(graph[pre][0] == 0) return; 	// 회사로 돌아가는 길이 없음
			
			ans = Math.min(ans, total + graph[pre][0]);
			return;
		}
		
		for(int i=1; i<N; i++) {
			if(visited[i] || graph[pre][i] == 0 ) continue;
							// 이전 집에서 올 수 없다면 continue
			visited[i] = true;
			if(total + graph[pre][i] < ans) perm(cnt+1, i, total + graph[pre][i]);
			visited[i] = false;
			
		}
	}
}