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

https://www.acmicpc.net/problem/2098

2098번: 외판원 순회

🔶 풀이

불특정한 도시 A에서 출발해서 한 바퀴를 돌고 도시 A로 다시 돌아왔을 때 최소 비용을 구하는 문제.

시간 제한이 적기 때문에 dp와 비트마스크를 활용해야함.

비트마스크(Bit Mask) 알고리즘 장점 및 연산자 사용 방법

위에서 말했듯이 외판원 순회는 싸이클 형태를 가지고 있다. 

때문에 출발 도시는 원하는 곳으로 설정해주면 된다.

 

dp 2차원 배열로 현재 위치한 도시와 비트마스크로 방문 여부를 확인한다.

dp[현재 방문한 도시][도시 방문 여부]

 

dp[1][0001] 현재 위치한 도시는 1번, 여태까지 방문한 도시는 1번 도시일 때 최소 비용

dp[2][0011] 현재 위치한 도시는 2번, 여태까지 방문한 도시는 1, 2번 도시일 때 최소 비용

dp[4][1111] 현재 위치한 도시는 4번, 여태까지 방문한 도시는 1, 2, 3, 4번 도시일 때 최소 비용

 

✅ 주의

모든 도시를 방문했을 때 시작 도시로 갈 수 없는 경우 나올 수 없을 정도의 큰 값(INF)으로 대체

: return을 시켜버리면 추후에 방문하는 상황이 생김 → 시간 초과

 

초기에 dp 배열을 -1로 초기화해주고, 방문했을 때 값이 없으면 INF 값으로 변경

: 처음부터 INF 값으로 초기화 → 시간 초과

  초기에 초기화했던 -1로 진행 → Math.min() 과정을 진행할 수 없음.

 

 

<최종코드>

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

public class Main {
    static int N, map[][], dp[][];
    static final int INF = 11000000;
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
		
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        dp = new int[N][1 << N];
		
        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());
            }
			
            Arrays.fill(dp[i], -1);
        }
		
        System.out.println(find(0, 1));
    }
	
    /**
     * 
     * @param cur 현재 도착한 도시
     * @param pos 현재 방문한 도시 상태값
     * @return
     */
    public static int find (int cur, int pos) {
        // 전부 방문한 경우
        if (pos == (1 << N) -1) {
            if (map[cur][0] == 0) return INF;
            return map[cur][0];
        }
		
        // dp 값이 존재하는 경우
        if (dp[cur][pos] != -1) return dp[cur][pos];
		
        dp[cur][pos] = INF;
			
        for (int i=0; i<N; i++) {
        
            // 길이 있고, 방문하지 않은 경우
            if ((pos & (1 << i)) == 0 && map[cur][i] != 0) {
                int next = (pos | (1 << i));
				
                dp[cur][pos] = Math.min(dp[cur][pos], find(i, next) + map[cur][i]);
            }
        }
        
        return dp[cur][pos];
    }
}