백준 10971번 : 외판원 순회 2 (Java)

🔗 문제 링크

10971번: 외판원 순회 2

📖 풀이 과정

- DFS 관련 유형의 문제입니다.

- 각 도시는 무조건 연결되어있다는 전제조건이 있습니다.

- 그래서, 어떤 도시에서 어떤 도시를 방문할 수 있는지 없는지는 신경쓰지 않아도 됩니다.

- 하지만, 결국에는 시작했던 도시에 다시 와야 합니다. 
  - 그래서, 메소드의 매개변수로 start한 도시가 계속해서 함께 포함됩니다.
  - depth 변수가 도시의 총 개수와 같아질 경우에는 현재 있는 도시에서 start 도시로 가는 비용을 추가해야 합니다.
  - 이렇게 계산된 총 비용을 Math.min() 메소드를 통해 최솟값을 구합니다.
  
- solve() 메소드에서는 DFS 방식으로 구현진행합니다.
  - 방문하지 않고, 비용이 양수일 경우에만 해당하는 도시를 방문하고 재귀적으로 진행합니다.

---

💻 코드

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

public class Main {
    static int cost;
    static int n;
    static int[][] arr;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = null;

        n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        visited = new boolean[n];
        cost = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < n; i++) {
            visited[i] = true;
            solve(i, i, 0, 0);
        }

        bw.write(cost + "");
        bw.flush();

        bw.close();
        br.close();
    }

    private static void solve(int start, int now, int depth, int sum) {
        if (depth == n - 1) {
            if (arr[now][start] != 0) {
                sum += arr[now][start];
                cost = Math.min(cost, sum);
            }
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!visited[i] && arr[now][i] > 0) {
                visited[i] = true;
                solve(start, i, depth + 1, sum + arr[now][i]);
                visited[i] = false;
            }
        }
    }
}