[BOJ] 10971번 외판원 순회 2 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {
    static int n, minSum = Integer.MAX_VALUE;
    static int[][] map;
    static boolean[] used;

    public static void main(String[] args) throws Exception {
        init();
        process();
        print();
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        StringTokenizer st;
        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());
            }
        }
    }

    private static void process() {
        for (int i = 0; i < n; i++) {
            used = new boolean[n];
            used[i] = true;
            dfs(1, i, i, 0);
        }
    }

    private static void dfs(int depth, int start, int now, int sum) {
        // 현재 비용의 합이 최소 비용보다 크다면 가지치기
        if (sum > minSum) {
            return;
        }
        // 전부 순회한 경우 최솟값 갱신
        if (depth == n && map[now][start] != 0) {
            sum += map[now][start];
            minSum = Math.min(sum, minSum);
            return;
        }
        // 현재 위치에서 갈 수 있는 모든 정점 탐색 수행
        for (int i = 0; i < n; i++) {
            if (!used[i] && map[now][i] != 0) {
                used[i] = true;
                dfs(depth + 1, start, i, sum + map[now][i]);
                used[i] = false;
            }
        }
    }

    private static void print() {
        System.out.println(minSum);
    }
}

📄 해설

• 외판원 순회의 기본적인 문제
• 시간과 메모리가 넉넉하므로 DFS 로 접근하여 풀이를 하면 되는 문제
• 출발도시가 정해지지 않았으므로, 모든 도시에 대해서 DFS 를 수행하였음. 아래는 구현의 세부
  • 방문 여부를 체크해서 모든 도시는 한번만 방문하도록함
  • 비용이 0인 경우는 가지 못하는 경우이므로, 해당 도시는 방문하지 않도록 함
  • 마지막 도시에 도착한 경우, 출발 도시로 갈 수 있으면 최솟값을 갱신

놓쳤던 부분

마지막 도시에서 출발 도시로 가는 경우는 무조건 존재하는 것으로 착각하였음