[Java] 백준 10971번 : 외판원 순회 2*

1. 문제

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

10971번: 외판원 순회 2

 

 

 

2. 풀이과정

1) 시작점 = 출발점이므로, 출발점은 어디든 결과는 같다. 따라서 시작점은 0으로 고정했다.

2) 순서에 따라 결과가 달라지는 순열 문제이다. 그리고 마지막에 도착지 => 출발지까지 값도 고려해주는 걸 잊지말자.

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

public class Boj10971 {
static int N, cost[][], result;
	
	public static void dfs(int x, int cnt, int sum, int visited) {
		if(cnt==N) {
			result = Math.min(result, sum+cost[x][0]);
			return;
		}
		for(int i=1; i<N; i++) {
			if((visited&(1<<i))==0) {
				dfs(i, cnt+1, sum+cost[x][i], visited|(1<<i));
			}
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		cost = new int[N][N];
		final int INF = 999_999_999;
		result = INF;
		StringTokenizer st = null;
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				cost[i][j] = Integer.parseInt(st.nextToken());
				cost[i][j] = (cost[i][j]==0) ? INF : cost[i][j];
			}
		}
		dfs(0, 1, 0, 1<<0);
		System.out.println(result);
	}
}