b2098. 외판원 순회

 

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

 

 

 

이 문제는 외판원 순회 문제를 해결하기 위해 동적 계획법과 비트마스크를 활용하였다.

먼저 도시 수 N과 도시 간 이동 비용을 입력받고, 이동 불가능한 경로는 INF로 설정한다.
dist 배열에는 각 도시 간의 이동 비용이 저장되고,
dp 배열은 특정 방문 상태와 현재 위치에서의 최소 비용을 저장하는 데 사용된다.

시작점인 0번 도시는 이미 방문한 상태로 초기화되며,
나머지는 초기값으로 설정된다.

tsp 메서드는 모든 도시를 방문하는 경로를 비트마스크로 나타내어 각 상태를 갱신한다.
현재 방문한 도시 집합과 위치를 기준으로,
다음에 방문할 도시를 확인하며 비용을 갱신한다.

만약 이미 방문한 도시거나,
이동이 불가능한 도시라면 건너뛴다.

모든 상태를 처리한 후,
마지막으로 모든 도시를 방문하고 시작점으로 돌아오는 경로 중
최소 비용을 계산하여 결과로 반환한다.

비트마스크를 이용해 방문 상태를 효율적으로 관리하며,
DP를 활용해 중복 계산을 방지한다.

비트마스크를 활용하여 문제를 풀려고 마음을 먹었고
비트마스크의 연산기호중 | , & , << 등과 같은 자주 사용되는 연산기호를 연습하는데

큰도움이 되는 문제였다.

 

문제를 풀이하는데 있어 앞으로 비트마스킹이라는 방문체크방식을 잘 사용하게 될 것 같다.

 

 

 

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

public class Main {

    static int N, INF = Integer.MAX_VALUE/2;
    static int[][] dist,dp;

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

        set(br);
        System.out.println(tsp());

    }

    private static int tsp() {
        int answer = INF;

        for (int visited = 0 ; visited < (1<<N) ; visited++){
            for (int current = 0 ; current < N ; current++){
                if((visited & (1 << current)) == 0) continue;
                for (int next = 0 ; next < N ; next++){
                    if(current == next) continue;
                    if((visited & (1 << next)) != 0 || dist[current][next] == INF) continue;
                    int nextVisited = (visited|(1<<next));
                    dp[nextVisited][next] = Math.min(
                            dp[nextVisited][next]
                            ,dp[visited][current]+dist[current][next]);
                }
            }
        }

        for (int now = 1 ; now < N ; now++){
            if(dist[now][0] == INF) continue;
            answer = Math.min(answer, dp[(1<<N)-1][now]+dist[now][0]);
        }

        return answer;
    }

    private static void set(BufferedReader br) throws IOException {
        N = Integer.parseInt(br.readLine());
        dist = new int[N][N];
        dp = new int[1<<N][N];

        for(int i = 0 ; i < N ; i++){
            dist[i] = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(s-> s.equals("0") ? INF : Integer.parseInt(s))
                    .toArray();
        }

        for(int[] arr : dp)
            Arrays.fill(arr,INF);

        dp[1][0] = 0;
    }
}