정올 1681 : 해밀턴 순환회로

Java

1681 : 해밀턴 순환회로

문제

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

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

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

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

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

문제출처

접근 방법

DFS과 백트래킹으로 해결하였다.

시작 노드 0에서 부터, n개 까지 반복하며, 방문하지 않았은 노드로 갈 수 있으면 그 가중치를 더하고 다음 DFS로 탐색하며 반복한다.

다음 노드로 방문할 때, 그 가중치의 합이 n개 만큼 노드를 방문하였을 때 얻은 가중치의 값보다 작을 때만 탐색하게 하여 Back Tracking을 수행하였다.

주의할 점은, 갈 수 없으면 0으로 표시 되어 있으므로 이 것을 처리해야한다.

코드

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

public class Main {
	static int n, result = Integer.MAX_VALUE;
	static int[][] graph;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());
    	graph = new int[n][n];
    	
    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < n; j++) {
    			graph[i][j] = stoi(stk.nextToken());
    		}
    	}
    	
    	DFS(0, 0, new boolean[n], 0);
    	
    	System.out.println(result);
    	br.close();
	}

	// 시그니처는 왼쪽에서 부터 [현재까지 뽑은 노드의 개수, 현재 노드, 방문 여부, 총 합]
	private static void DFS(int lv, int curN, boolean[] vis, int sum) {
		if(lv == n - 1) {		// n - 1개의 노드를 다 방문 하였을 시
			if(graph[curN][0] != 0) {	// 마지막 노드에서 첫 번째 노드로 갈 수 있으면
				sum += graph[curN][0];
				result = Math.min(result, sum);		// n개 만큼의 가중치의 최소 값을 갱신
			}
			return; 
		}
		
		vis[curN] = true;	// 방문한 노드는 방문 처리한다.
		
		for(int i = 1; i < n; i++) {
			// 방문하지 않은 노드이며 && 다음 노드의 합이 현재까지의 최소 값보다 작으며 && 이어져 있어 갈 수 있으면
			if(!vis[i] && sum + graph[curN][i] < result && graph[curN][i] != 0) {
				DFS(lv + 1, i, vis.clone(), sum + graph[curN][i]);
			}
		}
	}


	static int stoi(String str) {
    	return Integer.parseInt(str.replaceAll(" ", ""));
    }
}

총평

난이도

⭐⭐★★★

후기

문제의 조건 중 하나인, 이동 할 수 없는 경우는 0으로 구분해주어야 하는 것을 놓쳤다.

개선할 점

없