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

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

 

dfs로 모든 경우의 수를 구해준 뒤 각각의 경우에 수에 따라 값을 넣어주고 최소값을 출력하도록 만들어 줬다.

 

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

public class Main {

	public static int n, MIN = 10000000;
	public static int[][] a;
	public static int[] arr;
	public static boolean[] visit;
	public static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		a = new int[n][n];
		arr = new int[n];
		visit = new boolean[n];

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				a[j][i] = sc.nextInt();
			}
		}

		dfs(0);

		sb.append(MIN);

		System.out.println(sb);

	}

	public static void dfs(int depth) {
		if (depth == n) {
			int cnt = 0;
			for (int i = 1; i < n; i++) {
				if(a[arr[i-1]][arr[i]] != 0)
					cnt += a[arr[i-1]][arr[i]];
				else
					return;
			}
			if(a[arr[n - 1]][arr[0]] != 0)
				cnt += a[arr[n - 1]][arr[0]];
			else
				return;
			
			if(MIN > cnt) {
				MIN = cnt;
			}
			
			return;
		}

		for (int i = 0; i < n; i++) {
			if (!visit[i]) {
				visit[i] = true;
				arr[depth] = i;
				dfs(depth + 1);
				visit[i] = false;
			}
		}
	}
}