백준 10971

 

동적 계획법으로 풀 수 있다는데 아직 안배웠다. 그래서 재귀(백트래킹)로 풀었다.

 

어차피 n 수가 적기 때문에

1. 하나하나의 순열을 모두 구하고

2. 거쳐간 order의 비용이 모두 0이 아닌 경우에

3. answer와 비교를 통해서 답을 업데이트한다.

 

 

풀고 나서 생각난건데 visited[]에서 if문을 걸 때 &&을 활용해서 비용 조건도 그때 확인했다면 더 좋았을 것 같다.

 

package programers;

import java.util.Arrays;
import java.util.Scanner;

public class BOJ10971 {
    static int[][] graph;
    static boolean[] visited;
    static int answer = Integer.MAX_VALUE;
    static int[] order;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        graph = new int[n][n];
        order = new int[n];
        visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                graph[i][j] = sc.nextInt();
            }
        }
        recur(0, 0);
            System.out.println(answer);
    }

    public static boolean canGo(int a, int b) {
        return graph[a][b] != 0;
    }

    public static void recur(int depth, int sum) {
        if (depth == visited.length) {
            for (int i = 0; i < order.length - 1; i++) {
                if (!canGo(order[i], order[i + 1])) {
                    return;
                }
            }
            if (canGo(order[depth - 1], order[0])) {
                sum += graph[order[depth - 1]][order[0]];
                answer = Math.min(answer, sum);
            }
            return;
        }
        for (int i = 0; i < visited.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                order[depth] = i;
                int price = 0;
                if (depth > 0) {
                    price = graph[order[depth - 1]][order[depth]];
                }
                recur(depth + 1, sum + price);
                visited[i] = false;
            }
        }
    }
}