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

🔺 문제

2098번: 외판원 순회

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    private static final int INF = 1000000 * 16+ 1;
    private static int N;       // 도시 개수
    private static int[][] W;   // i → j 도시로 가는 데 드는 비용 저장 배열
    private static int[][] D;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        W = new int[16][16];
        D = new int[16][1 << 16];
        
        for(int i = 0 ; i < N ; i++) 
            Arrays.fill(D[i], INF);
        
        // W 배열에 값 저장
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine().trim());
            for(int j = 0 ; j < N ; j++) {
                W[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        System.out.println(tsp(0, 1));  // 완전 탐색
    }
    
    // 🔔 완전 탐색 메소드 🔔
    private static int tsp(int now, int visit) {
        // 모든 도시 방문 시
        if(visit == (1 << N) - 1)   
            return W[now][0] == 0 ? INF : W[now][0];
            
        // 이미 방문한 도시인 경우, 바로 리턴 (= 메모이제이션)
        if(D[now][visit] != INF)        
            return D[now][visit];
           
        for(int i = 0 ; i < N ; i++) { // 현재 도시에서 각 도시에 대해 dfs 수행
            // 방문한 적이 없고, 갈 수 있는 도시일 때
            if((visit & (1 << i)) == 0 && W[now][i] != 0)
               D[now][visit] = Math.min(D[now][visit], tsp(i, (visit | (1 << i))) + W[now][i]);
        }
 
        return D[now][visit];
    }
}

✅ 해결 아이디어
✔ DP + 비트 마스크
- D[c][v] : 현재 도시가 c, 현재까지 방문한 모든 도시 리스트가 v(비트마스크)일 때 앞으로 남은 모든 도시를 경유하는 데 필요한 최소 비용 ( i는 방문하지 않은 도시 )
- 점화식 : DP[node][visit] = min(DP[node][visit], DP[i][visit | (1 << i )] + W[node][i])
- W[c][i] : 도시 c에서 도시 i로 가기 위한 비용

- 방문 도시를 2진수로 표현
(예 : 4번, 1번 방문 → 1001 → D[ i ][ 9 ])

 

- 모든 도시 순회 판단 연산식 : if(v == 1 << N) - 1)

- 방문 도시 확인 연산식 : if(( v & ( 1 << i ) ) == 0 )

- 방문 도시 저장 연산식 : v | ( 1 << i )

---

🔺 다른 풀이들

- 과정 설명 굿!!! (복습용)

(JAVA) 백준 2098번 : 외판원 순회 --- [DP, TSP, 비트마스크]

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

[백준] 2098. 외판원 순회 (Java)

---

💬 느낀 점

이 자식(=나)은... 성장하기까지 아직 많이 남았습니다....

 

 

1회독	2회독	3회독	4회독	5회독
V	7/10

---

(참고)

✔ Do it 알고리즘 코딩테스트 자바편

✔ 외판원 순회 알고리즘 (TSP)

[JAVA] 외판원 순회 문제 (TSP) + 시간초과 해결방법

[백준 2098: JAVA] 외판원 순회 / dp + 비트 마스크