백준 10971번: 외판원 순회 2 [재귀][백트래킹][브루트포스] - Java

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

10971번: 외판원 순회 2

 

최소 비용의 경로를 구하는 문제

 

도시의 수 N이 최대 10까지 이므로 모든 도시를 방문하고 돌아와도 10번이다.

10*1,000,000 숫자범위를 사용한다.

 

N!의 가짓수가 나오기에 10!하여도 1초안에 계산 가능.

완탐 알고리즘 사용

 

 

<Java 코드>

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static int[][] map;
	public static boolean visit[];
	public static int N, res = Integer.MAX_VALUE;
	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];
		visit = new boolean[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());
			}
		}
		
		for (int i = 0; i < N; i++) {
			
			fun(i,i,0,0); //시작점은 1~N까지 모두 가능
		}
		
		
		System.out.println(res);
		
	}
	
	public static void fun(int start, int cur, int cnt, int sum) {
		if(cnt == N-1) {
			if(map[cur][start]>0) {
				sum += map[cur][start]; //출발지로 가기 위한 마지막 비용 계산
				res = Math.min(res,sum);
			}
			return;
		}
		
		for (int i = 0; i < N; i++) {
			if(start==i) //출발지인가?
				continue;
			if(visit[i]) //이미 들른 도시인가?
				continue;
			if(map[cur][i] <= 0) //갈 수있는 곳인가?
				continue;
			
			visit[i] = true;
			fun(start,i,cnt+1,sum+map[cur][i]);
			visit[i] = false;
		}
	}

}