백준 5901번: Relocation (Java)

접근

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

5901번: Relocation

문제해석: 농부 존은 이사를 가는데 어디로 이사 가야 할지 결정하려고 합니다. 도시는 N개 있고, 이 도시들은 M개의 도로로 연결되어 있으며, N개의 도시 중 K개의 도시만이 마켓을 가지고 있습니다. 도시들은 적어도 한개 이상의 도로로 연결되어 있습니다. 존은 집값의 이유로 마켓이 있는 도시로는 이사가지 않지만 매일 이 K개의 마켓 모두를 들러야하기 때문에, 집에서 출발하여 모든 마켓을 돌고 다시 집으로 돌아오는데까지 걸리는 거리를 최소로 하는 도시를 선택하려고 합니다. 그 거리를 구하는 문제입니다.

다익스트라 알고리즘과 도시들의 방문 순서를 DFS로 조합하여 문제를 해결할 수 있습니다.

처음에는 기본적인 다익스트라 문제처럼 N개의 도시에서 출발하는 다익스트라를 모두 구하여 N * N 배열을 모두 채우고, d[N][k1] + d[k1][k2] + ... + d[k5][N] 을 구하려고 하였으나 메모리 초과로 실패하였습니다.

생각해보니 이 문제에서 길의 방향성이 없다는 것을 깨닫고 마켓이 있는 도시에서 출발하는 다익스트라만 계산하여 문제를 해결하였습니다.

DFS 알고리즘을 통해 K개 마켓의 방문 순서를 결정하고, 방문 순서가 정해지면 d[k1][N] + d[k1][k2] + ... + d[k5][N] 를 1번부터 N번까지 모든 도시에 대하여 계산하여 최소값을 갱신하면서 탐색을 진행하면 문제를 해결할 수 있습니다.

코드

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

public class Main {

  static int N, M, K;
  static int ans = Integer.MAX_VALUE;
  static ArrayList<Integer> market;
  static ArrayList<Pair>[] road;
  static int[][] distance;
  static boolean[] visited;

  static class Pair implements Comparable<Pair> {

    private int dest, dist;

    public Pair(int dest, int dist) {
      this.dest = dest;
      this.dist = dist;
    }

    @Override
    public int compareTo(Pair o) {
      return this.dist - o.dist;
    }
  }

  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());
    M = Integer.parseInt(st.nextToken());
    K = Integer.parseInt(st.nextToken());
    market = new ArrayList<>();
    road = new ArrayList[N + 1];
    distance = new int[K][N + 1];
    for (int i = 0; i < K; i++) {
      for (int j = 1; j <= N; j++) {
        distance[i][j] = Integer.MAX_VALUE;
      }
    }
    for (int i = 1; i <= N; i++) {
      road[i] = new ArrayList<>();
    }
    for (int i = 1; i <= K; i++) {
      market.add(Integer.parseInt(br.readLine()));
    }
    for (int i = 0; i < M; i++) {
      int a, b, d;
      st = new StringTokenizer(br.readLine());
      a = Integer.parseInt(st.nextToken());
      b = Integer.parseInt(st.nextToken());
      d = Integer.parseInt(st.nextToken());
      road[a].add(new Pair(b, d));
      road[b].add(new Pair(a, d));
    }
    br.close();
    // K개의 마켓을 시작점으로 하는 다익스트라만 계산
    for (int i = 0; i < K; i++) {
      dijkstra(i);
    }
    for (int i = 0; i < K; i++) {
      visited = new boolean[K];
      visited[i] = true;
      dfs(i, i, 1, 0);
    }
    System.out.println(ans);
  }

  // 시작 마켓, 마지막 방문 마켓, depth, distance를 저장하는 dfs
  static void dfs(int start, int last, int n, int d) {
    if (n == K) {
      // K개의 마켓을 모두 방문하면, 처음 마켓~N마을 거리 + 마지막 마켓~N마을 거리를 더해준 값을 비교
      for (int i = 1; i <= N; i++) {
        if (!market.contains(i)) {
          ans = Math.min(ans, d + distance[start][i] + distance[last][i]);
        }
      }
      return;
    }
    for (int k = 0; k < K; k++) {
      if (visited[k]) continue;
      visited[k] = true;
      dfs(start, k, n + 1, d + distance[last][market.get(k)]);
      visited[k] = false;
    }
  }

  // 다익스트라 알고리즘
  static void dijkstra(int index) {
    int start = market.get(index);
    distance[index][start] = 0;
    PriorityQueue<Pair> queue = new PriorityQueue<>();
    queue.add(new Pair(start, 0));
    while (!queue.isEmpty()) {
      Pair now = queue.poll();
      if (distance[index][now.dest] < now.dist) continue;
      for (int i = 0; i < road[now.dest].size(); i++) {
        Pair ne = road[now.dest].get(i);
        int next = ne.dest;
        int nextDistance = now.dist + ne.dist;
        if (nextDistance < distance[index][next]) {
          distance[index][next] = nextDistance;
          queue.add(new Pair(next, nextDistance));
        }
      }
    }
  }
}

더 생각해 볼 것?

...

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