[JO] 정올 1681 해밀턴 순환회로 (JAVA)

문제

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=954&sca=99&sfl=wr_hit&stx=1681

 

풀이 방법

태현이는 배달 알바를 하려고 한다. 배달을 하기 위해 방문할 장소가 주어졌을때, 방문하는 순서에 따라서 비용이 달라진다. 최소의 비용을 계산하는 문제이다.

나는 dfs를 사용해서 문제를 풀었다. 0번째부터 시작하면서 모든 경우의 수를 다 따져봤다.
그러면서 시간초과를 막기 위해서 if문으로 끝까지 배달을 못했어도 현재 min값보다 sum의 값이 더 커지면 return을 하면서 백트래킹을 해줬다.

 

제출 코드

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

public class JO_1681_해밀턴순환회로 {
	static int min, N;
	static boolean[] visited;
	static int[][] map;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());

		map = new int[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		min = Integer.MAX_VALUE;
		dfs(0, 0, 0, new boolean[N]); // 0번부터 시작, 비용의 합, 들린장소의 수 , 방문체크 배열
		System.out.println(min);
	}

	private static void dfs(int i, int sum, int cnt, boolean[] visited) {
		if (sum > min) //중간에 sum이 현재의 최소값을 넘으면 중단
			return;

		visited[i] = true; // 방문 체크

		if (cnt == N - 1) {
			if(map[i][0]==0) return; //마지막에 선택된 장소가 회사로 갈 수 있는 길이 없으면 중단
			sum += map[i][0];
			min = Math.min(min, sum);
			return;
		}

		for (int j = 1; j < N; j++) {
			if (!visited[j] && map[i][j] != 0) {
				boolean[] nvisited = Arrays.copyOf(visited, N);
				dfs(j, sum + map[i][j], cnt + 1, nvisited); //재귀 호출
			}
		}

	}
}