[백준] 17182: 우주 탐사선 (비트마스킹, Floyd-Warshall, dfs 메모이제이션) - JAVA

# 문제

 

 

# 예제

입력 : 첫 번째 줄에는 행성의 개수 N과 ana호가 발사되는 행성의 위치 K가 주어진다. (2 ≤ N ≤ 10, 0 ≤ K < N)

다음 N 줄에 걸쳐 각 행성 간 이동 시간 Tij 가 N 개 씩 띄어쓰기로 구분되어 주어진다. (0 ≤ Tij  ≤ 1000)

4 1
0 83 38 7
15 0 30 83
67 99 0 44
14 46 81 0

 

출력 :  모든 행성을 탐사하기 위한 최소 시간을 출력한다. 

74

 

# 필요개념

 

너무 오랜만에 최단거리 문제를 풀어서 방식을 생각하는 데 시간이 조금 걸렸다. 중복에 관한 조건이 없었다면, 단순 그래프로 풀었을 거 같지만 문제 조건 중 "이미 방문한 행성도 중복해서 갈 수 있다" 라는 조건이 있었기 때문에 플로이드-워셜 알고리즘을 이용해야 겠다고 생각했다.

 

✅ 플로이드-워셜 알고리즘 (Floyd-Warshall algorithm)

플로이드-워셜 알고리즘은 쉽게 이야기하면 해당 노드를 경유했을 때와 직항일 때를 비교해 최솟값을 채워넣는 알고리즘으로 삼중 반복문을 이용하는 비교적 간단한 알고리즘이다.

 

아래 글에 간단하게 정리해두었다.

https://wanna-developer02.tistory.com/50

[알고리즘] CHAP 3. Graph Theory (그래프) - 그래프로 최단거리 구하기

 

해당 문제에서는 중복이 가능했기 때문에, 배열을 플로이드 워셜로 전처리하고나면, 전처리 된 배열 자체가 중복을 고려한 결과값이니까까 중복을 신경쓰지 않고 탐색해도 괜찮지 않을까? 라는 생각으로 이용했다.

 

 

전처리를 한 후에는 dfs를 이용해 탐색하면 되겠다! 라는 생각을 했다. bfs가 아닌 dfs를 선택한 이유는 재귀를 통해 a부터 b까지의 최솟값을 반환해서 바로 이용하는 게 효율적일 것이라고 판단했기 때문이다. 이때 한 가지 고민이 되었던 부분은, 방문 노드를 어떻게 체크하는게 좋을까? 였다. 파라미터로 배열을 넘기면서 방문 여부를 체크해도 괜찮았겠지만, 모든 노드를 탐색했는가를 파악할 때마다 반복문을 돌려야 하기 때문에 번거롭다고 생각했다. 그래서 생각한 게 비트마스킹이었다.

 

 

✅ 비트 마스킹

비트마스킹을 이용하면, 숫자를 비트로 다룰 수 있다! 예를 들어, 0번째 노드만 방문했다고 가정하면 1 << 0 을 이용해 방문여부를 판단할 수 있다. 비트 연산자는 |, & 등을 이용할 수 있고, 해당 부분은 아래 블로그에 정리되어있다.

https://wanna-developer02.tistory.com/180

[백준] 9527 : 1의 개수 세기 (DP, 비트마스킹, 누적합) - JAVA

 

그래서 결론적으로는 N이 4라면, 1111 인 경우 모든 노드를 방문했다고 봐도 되기 때문에 이를 종료조건으로 활용해 문제를 풀었다. 비트마스킹과 dfs 메모이제이션을 이용해 배열에 최솟값을 누적해 저장하는 방식으로 문제풀이를 진행했다.

 

 

# Code

package Baekjun;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

// 17182 (중복 가능 -> 플로이드-워셜 알고리즘 사용)
public class Main {
    static int N;
    static int startIdx;
    static int[][] arr;
    static int[][] dp;
    public static void main(String[] args) throws IOException {
        fillArray();
        floyd(); // 중복 허용 경로까지 탐색한 최단거리, 근데 중간에 어디를 거쳤는지 모름
        fillDp();
        int ans = explore(startIdx, 1 << startIdx);
        System.out.println(ans);
    }

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

    private static int explore(int nowIdx, int isVisit) {
        if (isVisit == (1 << N) - 1) return 0;
        if (dp[nowIdx][isVisit] != -1) return dp[nowIdx][isVisit];

        int min = Integer.MAX_VALUE;
        for (int i = 0 ; i < N ; i++) {
            if ((isVisit & 1 << i) == 0) {
                int time = arr[nowIdx][i] + explore(i, isVisit | (1 << i));
                min = Math.min(min, time);
            }
        }
        return dp[nowIdx][isVisit] = min;
    }

    private static void floyd() {
        for (int k = 0 ; k < N ; k++) {
            for (int i = 0 ; i < N ; i++) {
                for (int j = 0 ; j < N ; j++) {
                    arr[i][j] = Math.min(arr[i][k] + arr[k][j], arr[i][j]);
                }
            }
        }
    }

    private static void fillArray() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        startIdx = Integer.parseInt(st.nextToken());

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

 

# 결과