백준 17182번: 우주 탐사선 (Java)

접근

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

17182번: 우주 탐사선

행성의 수가 작고, 이미 방문한 행성을 다시 방문할 수 있으므로 플로이드 와샬 알고리즘을 사용하기로 했습니다. 추가적으로 백트래킹 알고리즘과 dp를 이용하였고, 행성의 수가 작으므로 dp에 비트마스크를 추가적으로 이용하기로 합니다.

하나의 정점에서 다른 모든 정점까지의 최단거리를 구하는 다익스트라와는 달리, 플로이드 와샬 알고리즘은 한번의 탐색으로 모든 노드 간 최단거리를 구할 수 있습니다. 다만, 시간복잡도가 O(n^3)이므로 그래프의 크기가 작을 때 이용하면 좋습니다.

K번 행성에서 출발하여 모든 정점을 방문하는 최단거리를 구하기 위해 dp와 비트마스킹을 이용하기 때문에 dp는 [1 << N][N] 으로 초기화해주고, 백트래킹을 진행해줍니다. 비트마스크를 이용하지 않는다면, visit 배열을 만들고 백트래킹 과정중에 모든 행성을 방문하였을 때마다 그 이동거리 값의 최소값을 따로 갱신해준다면 동일하게 문제를 해결할 수 있습니다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

public class Main {

  static int N, K;
  static int[][] dist;
  static int[][] dp;
  static int allvisit;

  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());
    dist = new int[N][N];
    dp = new int[1 << N][N];
    for (int i = 0; i < N; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < N; j++) {
        dist[i][j] = Integer.parseInt(st.nextToken());
      }
    }
    br.close();
    // 플로이드 와샬 알고리즘을 수행하여 dist 배열에 각 노드간의 최단거리를 갱신
    FloydWashall();
    for (int i = 0; i < N; i++) {
      allvisit = (allvisit | 1 << i);
    }
    // 백트래킹을 진행하고 그 결과를 출력
    System.out.println(dfs(1 << K, K));
  }

  // 플로이드 와샬 알고리즘 수행
  static void FloydWashall() {
    for (int k = 0; k < N; k++) {
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
          dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
        }
      }
    }
  }

  // 비트마스크를 이용한 백트래킹 탐색
  static int dfs(int visit, int idx) {
    if (dp[visit][idx] != 0) return dp[visit][idx];
    if (visit == allvisit) return dp[visit][idx] = 0;
    int ret = Integer.MAX_VALUE;
    for (int next = 0; next < N; next++) {
      if (idx == next || (visit & (1 << next)) != 0) continue;
      ret = Math.min(ret, dfs((visit | (1 << next)), next) + dist[idx][next]);
    }
    return dp[visit][idx] = ret;
  }
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!