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

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

2098번: 외판원 순회

---

2. 내가 푼 방법

비트마스크를 이용한 DP 알고리즘 문제이다. TSP 알고리즘을 몰랐기 때문에 다른 분들의 풀이를 참고했다.

 

이미 방문한 적 있는 노드를 저장하기 위해 int[][] dp = new int[N][(1 << N) -1]; 을 선언하고 -1로 초기화했다.

또한 이제 각 노드를 방문할텐데 여기서 중요한 것이 비록 모든 노드를 방문하는 경로가 아니어도, 방문했다는 표시를 해주는 것이다.

public static int tsp(int city, int bit) {
    if (bit == (1 << N) - 1) {
        if (arr[city][0] == 0) return INF;
        else return arr[city][0];
    }

    if (dp[city][bit] != -1) return dp[city][bit];

    // 방문처리
    dp[city][bit] = INF;

    for (int i = 0; i < N; i++) {
        // 경로가 없거나 이미 방문했을 경우
        if (arr[city][i] == 0 || (bit & (1 << i)) != 0) continue;

        int next = bit | (1 << i);

        dp[city][bit] = Math.min(dp[city][bit], tsp(i, next) + arr[city][i]);
    }

    return dp[city][bit];
}

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B2098.java

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

class Main {
    static int N;
    static int[][] arr;
    static int[][] dp;
    static int INF = 1000000 * 16;
    static int result;

    public static void main (String[] args) throws IOException {
        init();
        solution();
        print();
    }

    public static void solution() {
        result = tsp(0, 1);
    }

    public static int tsp(int city, int bit) {
        if (bit == (1 << N) - 1) {
            if (arr[city][0] == 0) return INF;
            else return arr[city][0];
        }

        if (dp[city][bit] != -1) return dp[city][bit];

        // 방문처리
        dp[city][bit] = INF;

        for (int i = 0; i < N; i++) {
            // 경로가 없거나 이미 방문했을 경우
            if (arr[city][i] == 0 || (bit & (1 << i)) != 0) continue;

            int next = bit | (1 << i);

            dp[city][bit] = Math.min(dp[city][bit], tsp(i, next) + arr[city][i]);
        }

        return dp[city][bit];
    }

    public static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(result+"");

        bw.flush();
        bw.close();
    }

    public static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        arr = new int[N][N];
        dp = new int[N][(1 << N) - 1];

        for (int i = 0; i < N; i++) {
            Arrays.fill(dp[i], -1);
        }

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        br.close();
    }
}

---

4. 결과 및 회고

내일이나 모레 다시 한번 풀어봐야겠다. 비트마스크를 이용한 DP,, 머릿속에 저장해두기

TSP 알고리즘에 대해서 정리해서 포스팅해야겠다.