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

🔺 문제

10971번: 외판원 순회 2

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[][] map;
    static boolean[] visited;
    
    static int min;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        
        map = new int[N][N];
        for(int i = 0 ; i < N ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < N ; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        min = Integer.MAX_VALUE;
        visited = new boolean[N];
        
        for(int i = 0 ; i < N ; i++) { // 모든 도시를 출발지로 지정해 dfs 한 번씩 수행
            visited[i] = true;
            tsp(i, i, 0, 0);
        }
        
        System.out.println(min);
    }
    
    private static void tsp(int start, int now, int sum, int cnt) { // 시작 도시, 현재 도시, 총 비용, 깊이
        if(cnt == N - 1) {
            // 맨 마지막 노드 → 맨 처음 노드 루트 존재하는 경우
            if(map[now][start] != 0) {
                sum += map[now][start];
                min = Math.min(min, sum);
            }
            return;
        }
        
        for(int i = 0 ; i < N ; i++) {
            //  도시 i를 방문한 적 없고, 도시 i로 가는 루트가 존재하는 경우
            if(!visited[i] && map[now][i] != 0) {
                visited[i] = true;
                tsp(start, i, sum + map[now][i], cnt + 1);
                visited[i] = false;
            } 
        }
    }
}

✅ 해결 아이디어
✔ 백트래킹 (외판원 순회, TSP)
- [인자로 가져갈 값] ① 시작점 도시, ② 현재 도시, ③ 합, ④ 수행 횟수
- 방문한 적 없고, 비용이 양수인 경우에만 해당하는 도시를 방문하고 재귀적으로 진행

 

💥 유의사항

• 모든 노드 방문한 경우 ⇨ 처음 노드는 위에서부터 방문했으므로 N - 1

• 모든 도시를 출발지로 지정해 dfs 한 번씩 수행 (출발점 지정 안 했으므로)

• "한 번 방문했던 도시는 다시 방문할 수 없다." => 방문 여부 체크

 

---

🔺 다른 풀이들

- 다들 비슷하심

 

---

💬 느낀 점

우와 백트래킹 감 잡았다고 생각했는데 경기도 오산이었다.....

쉽지 않구나...

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[백준] 10971번 외판원 순회 2 - Java, 자바

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

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

 

- 그림 과정 포함

[백준 10971번] 외판원 순회 2 (java)