[JUNGOL] 해밀턴 순환회로

👀 문제 설명

문제

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

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

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

 

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

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

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

 

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

 

입력

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

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

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

 

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

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

 

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

 

출력

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

 

예제 입력 1

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

 

예제 출력 1

30

 

✍🏻풀이

DFS를 사용해 풀었다.

 

회사(1번)에서 시작해서 1번과 연결된 곳. 즉, 이동할 수 있는 곳으로 이동시킨다. (DFS 사용)

이 때, 무작정 모든 곳으로 이동시키는 게 아니라 최소 비용을 저장하는 ans와 이동시킨 후의 비용을 비교해서, 이동시킨 후의 비용이 더 작은 경우에만 이동시켜준다.

-> 최소 비용을 구하는 것이기 때문에, 현재까지의 최소 비용보다 큰 경우에는 어차피 답이 될 수 없으므로 이동시켜줄 필요가 없다.

 

코드

package jungol;

// 해밀턴 순환회로 (http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=954&sca=99&sfl=wr_hit&stx=1681 )

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

public class JUNGOL_1681 {
	
	private static int N;
	private static int[][] map;
	private static int ans = Integer.MAX_VALUE;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		// input
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		map = new int[N + 1][N + 1];
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			
			for (int j = 1; j <= N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		// solve
		for (int i = 2; i<= N; i++) {
			boolean[] visited = new boolean[N + 1];
			visited[1] = true;
			
			if (map[1][i] != 0) {
				visited[i] = true;
				dfs(i, map[1][i], visited);
			}
		}
		
		bw.write(ans + "\n");
		
		bw.flush();
		bw.close();
	}
	
	private static void dfs(int cur, int curCost, boolean[] visited) {
		// 모두 방문했는지 확인
		boolean canMoved = false;
		for (int i = 1; i <= N; i++) {
			if (!visited[i]) {
				canMoved = true;
				break;
			}
		}
		if (!canMoved) { // 모두 방문했으면 다시 1로 이동하고 리턴
			if (map[cur][1] != 0) // 마지막 방문한 지점에서 1로 이동할 수 있는지 확인하고, 이동할 수 있을 경우
				ans = Math.min(ans, curCost + map[cur][1]); // ans와 curCost + map[cur][1] (현재 값 + 1로 이동할 값) 중 더 작은 값을 ans에 넣는다.
			return;
		}
		
		// 아직 방문할 곳이 남은 경우
		for (int i = 1; i <= N; i++) {
			// 1. 방문하지 않은 곳이면서 2. 현재 지점과 연결되어 있는 곳, 3. 이동 후의 값이 ans보다 작을 경우에만!
			// 이동시킨다.
			if (!visited[i] && map[cur][i] != 0 && curCost + map[cur][i] < ans) {
				visited[i] = true; 
				dfs(i, curCost + map[cur][i], visited); // i번으로 이동
				visited[i] = false; // 현재 지점에서 또 다른 곳으로 이동할 수도 있기 때문에 visited[i]를 다시 false로 바꿔준다.
			}
		}
	}

}