BOJ_10971 : 외판원 순회 2

👉 문제링크

10971번: 외판원 순회 2

---

---

🔸 문제 분석 🔸

• N개의 도시에서 모든 도시를 방문하고 마지막에 출발지로 돌아오는 여행 경로 중 가장 적은 비용을 출력한다.
• 재귀와 백트래킹을 통해 구현한다.

🔸 코드 🔸

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

public class Main {
    private static int N, W[][], MIN, ans, city;
    private static boolean[] visited;

    private static void recursion(int now, int cost, int cnt) {
        if (cost > MIN) {
            return;
        }
        if (cnt == N) {
            if (W[now][city] > 0) {
                cost += W[now][city];
                MIN = Math.min(MIN, cost);
            }
            return;
        }
        for (int i = 0; i < N; i++) {
            if (!visited[i] && W[now][i] > 0) {
                visited[i] = true;
                recursion(i, cost + W[now][i], cnt + 1);
                visited[i] = false;
            }
        }
    }

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

        N = Integer.parseInt(br.readLine());
        W = new int[N][N];

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

        // Recursion
        ans = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            city = i;
            MIN = Integer.MAX_VALUE;
            visited = new boolean[N];
            visited[i] = true;
            recursion(i, 0, 1);
            ans = Math.min(ans, MIN);
        }

        // Output
        System.out.println(ans);
    }
}

🔸 코드 해석 🔸

• 모든 도시를 한 번씩 출발지(도착지)로 두고, 재귀 메서드 recursion()을 호출한다.
  • recursion() 안에서 하나씩 방문해 본다.
  • 모든 도시를 방문했으면 비용을 계산해 최소값을 저장한다.
• 비용을 누적해서 재귀 메서드를 호출하는 방식으로, 전체 비용 계산의 중복을 줄인다.
  • 이미 찾은 비용보다 현재 누적 비용이 커졌으면, 볼 필요도 없으므로 리턴한다.

---

🔸 end 🔸

• 재귀를 구현하는건 간단하지만, 각 비용이 최대 100만까지 가므로 백트래킹이 꼭 필요했다.