[백준 10971] 외판원 순회 2 (자바)

 

https://www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

 

난이도 : 실버 2

 

DFS로 풀 수 있는 문제입니다.

방문 가능한 나라를 방문시 비용을 모두 더해준 후 마지막 방문지에서 출발지로 가는 비용을 더해주면 됩니다.

문제를 깊게 생각 안하고 풀었는데 놓친 것이 있었습니다.

예를들어 1, 2, 3, 4 순으로 방문을 했을 때 마지막 방문지인 4에서 출발지인 1로 갈 수 없는 경우를 생각 못 했습니다.

 

---

전역 변수 

n = 나라의 개수

map[][] = 나라별 이동시 발생하는 비용

answer = 나라별 이동 비용의 최소값visit[] = 나라의 방문 여부를 확인하는 배열

메소드

void main 

입력을 받은 후 출발지의 번호로 dfs를 시작합니다. (dfs 호출)

void dfs

모든 나라를 방문했는지 확인하고 방문했다면 출발지로 돌아갈 수 있는지를 확인합니다.

모든 조건이 참이라면 answer 값을 최적화해줍니다.

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

public class p10971 {
	static int n, map[][], answer;
	static boolean visit[];
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		StringTokenizer stz;
		map = new int[n+1][n+1];
		visit = new boolean[n+1];
		answer = Integer.MAX_VALUE;

		for(int i = 1; i <= n; i++) {
			stz = new StringTokenizer(br.readLine());
			for(int j = 1; j <= n; j++)
				map[i][j] = Integer.parseInt(stz.nextToken());
		}

		for(int i = 1; i <= n; i++) {
			visit[i] = true;
			dfs(i, i, 0);
			visit[i] = false;
		}
		
		System.out.println(answer);
	}

	public static void dfs(int start, int line, int sum) {
		boolean finish = true;
		for(int i = 1; i <= n; i++) 
			if(!visit[i]) 
				finish = false;
		
		if(finish && map[line][start] != 0) {
			answer = Math.min(answer, sum+map[line][start]);
			return;
		}
		
		for(int i = 1; i <= n; i++) {
			if(map[line][i] != 0 && !visit[i]) {
				visit[i] = true;
				dfs(start, i, sum + map[line][i]);
				visit[i] = false;
			}
		}
	}
}