104. 우주 탐사선 (백준 17182) [JAVA]

문제

문제 링크 : https://www.acmicpc.net/problem/17182

17182번: 우주 탐사선

문제

우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위치와 ana호가 행성 간 이동을 하는데 걸리는 시간이 2차원 행렬로 주어진다. 행성의 위치는 0부터 시작하여 0은 행렬에서 0번째 인덱스에 해당하는 행성을 의미한다. 2차원 행렬에서 i, j 번 요소는 i 번째 행성에서 j 번째 행성에 도달하는데 걸리는 시간을 나타낸다. i와 j가 같을 때는 항상 0이 주어진다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하여라.

탐사 후 다시 시작 행성으로 돌아올 필요는 없으며 이미 방문한 행성도 중복해서 갈 수 있다.

입력

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

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

출력

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

풀이

다시 방문한 행성을 재방문할 수 있다는 점이 어려운 부분인 것 같았다.

이를 위해서 기본적인 베이스는 BFS로 하고,

DP로 방문한 행성들의 목록을 2진수로 표현하게 하여 BFS에서의 중복을 검사하였다.

예를 들어 0,2,4 행성을 방문한 우주선이 i를 방문하려 할때 -> 10101(2) -> dp[21] [i] 체크

이때 최대 N의 개수가 10개이므로 -> 1111111111(2) = 1023이기 때문에

1023 * 10 * 4 = 40920B -> 40KB 정도로 메모리의 부담이 적어 가능할 것이라고 판단하였다.

또한 비교의 편의를 위해, 자기 자신으로 향하는 시간과 DP는 99999로 초기화하였다.

 

이후 모든 BFS 사이클을 돈 다음에는 DP[1023]을 모두 체크해서 가장 작은 값을 찾으면 된다.

 

다른 사람들의 풀이를 살펴보니, 플로이드 와샬 알고리즘으로 각 행성에서 다른 행성까지의 최소거리를 구한 다음,

재귀를 사용하여 행성 방문을 체크하며 진행하는 방법으로 간단하게 풀 수도 있었던 것 같다.

코드

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

public class Main {

    static int N;
    static int K; //start point
    static int[][] map;
    static int[][] dp;
    static int bp;
    static int answer = 99999;

    static HashMap<String, Integer> hashMap = new HashMap<>();

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

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        map = new int[N][N];
        bp = (1<<N)-1;
        dp = new int[bp+1][N];

        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++){
                if(i==j) {
                    map[i][j] = 999999;
                    st.nextToken();
                }
                else map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        BFS(K);
        for(int i=0; i<N; i++){
            answer = Math.min(answer, dp[bp][i]);
        }
        System.out.println(answer);
    }

    public static void BFS(int init){
        Queue<SpaceShip> q = new LinkedList<>();
        q.add(new SpaceShip(1<<init,init,0));
        
        //dp 초기화
        for(int i=0; i<dp.length; i++){
            for(int j=0; j<N; j++){
                dp[i][j] = 999999999;
            }
        }


        while (!q.isEmpty()){
            SpaceShip cur = q.poll();
            
            //다 돌았으면 얘는 종료
            if(cur.route == bp){
                continue;
            }

            int nextRoute;
            for(int i=0; i<N; i++){
                //자기 자신으로 반복은 X
                if(i == cur.start) continue;

                nextRoute = cur.route | (1<<i);
                
                if(dp[nextRoute][i] > map[cur.start][i] + cur.times){
                    dp[nextRoute][i] = map[cur.start][i] + cur.times;
                    q.add(new SpaceShip(nextRoute,i,dp[nextRoute][i]));
                }
            }
        }
    }
}

class SpaceShip{
    int route;
    int start;
    int times;
    //지나온 경로, 출발점, 누적 시간
    public SpaceShip(int r, int d, int t){
        this.route = r;
        this.start = d;
        this.times = t;
    }
}

결과