문제

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

---

입력

• 테스트케이스의 수
• N, M
• M개의 비밀통로
• 참석자 K명
• K명의 방 위치

---

출력

• 각 테스트 케이스마다 모임에 참여하는 친구들의 이동 거리의 총합이 최소가 되도록 하는 모임 장소의 방 번호를 출력한다.

---

풀이

제한조건

• 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 500
• 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 500
• land[i][j]는 i+1행 j+1열 땅의 정보를 나타냅니다.
• land[i][j]는 0 또는 1입니다.
• land[i][j]가 0이면 빈 땅을, 1이면 석유가 있는 땅을 의미합니다.

접근방법

Dijkstra 또는 Floydwarshall
문제를 읽어보면 2가지 방식으로 해결 가능함을 알 수 있다.

1. Dijkstra

참석자가 있는 K개의 방에서 다른 방까지의 최단거리를 구한다.

각각의 다익스트라를 수행한 결과를 하나의 배열에 합쳐주도록 하자.

그럼 전체 참석자들이 i번 방으로 가기 위한 최종 비용을 계산할 수 있다.

이제 N개의 방 중에서 가장 비용이 작으며 번호가 빠른 방으로 이동하면 된다.

2. Floydwarshall

플로이드 워셜을 통해서 모든 방의 이동에 대한 비용을 계산한다.

참석자들이 있는 K개의 방들만 선택해서 하나의 배열에 합쳐주면 된다.

그럼 1번 방식과 2번 방식이 무엇이 다른가?

1번 방법에서는 참석자들이 있는 K개의 방에서 각각 다익스트라를 통해 최단거리를 계산한다.
반면 2번 방법에서는 모든 비용계산을 한 번에 수행하고
K개의 방에서 원하는 값만 골라내는 방식이다.

K의 범위가 최대 N까지 가능하므로 최대치로 계산해보자면
다익스트라를 사용한다면, O(KMlogN) = O(N^3logN)
플로이드워셜의 경우 O(N^3)
이라고 볼수 있다.

• 다익스트라
  
• 플로이드 워셜
  

---

코드

• 다익스트라

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
    static class Node implements Comparable<Node> {
        int to;
        int weight;

        public Node(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node o) {
            return this.weight - o.weight;
        }
    }

    static List<Node>[] list;
    static StringBuilder sb = new StringBuilder();
    static int N, M, K;
    static int[] dist;
    static int[] sum;
    static int MAX = 987654321;

    public static void main(String[] args) throws Exception {
        // input
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = stoi(in.readLine());
        for (int tc = 0; tc < T; ++tc) {
            String[] inputs = in.readLine().split(" ");
            N = stoi(inputs[0]);
            M = stoi(inputs[1]);

            list = new List[N];
            for (int i = 0; i < N; ++i)
                list[i] = new ArrayList<>();
            for (int i = 0; i < M; ++i) {
                inputs = in.readLine().split(" ");
                int a = stoi(inputs[0]) - 1;
                int b = stoi(inputs[1]) - 1;
                int c = stoi(inputs[2]);
                list[a].add(new Node(b, c));
                list[b].add(new Node(a, c));
            }

            K = stoi(in.readLine());
            inputs = in.readLine().split(" ");
            sum = new int[N];
            for (int i = 0; i < K; ++i) {
                int value = stoi(inputs[i]) - 1;
                dist = new int[N];
                Arrays.fill(dist, MAX);
                dijkstra(value);
                for (int j = 0; j < N; ++j)
                    sum[j] += dist[j];
            }

            int idx = -1;
            int min = MAX;
            for (int i = 0; i < N; ++i) {
                if (sum[i] < min) {
                    idx = i + 1;
                    min = sum[i];
                }
            }
            sb.append(idx).append("\n");
        }
        System.out.println(sb);
    }

    private static void dijkstra(int start) {
        boolean[] check = new boolean[N];
        dist[start] = 0;
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        while (!pq.isEmpty()) {
            Node cur = pq.poll();
            if (check[cur.to] == true)
                continue;
            check[cur.to] = true;
            for (Node next : list[cur.to]) {
                if (dist[next.to] > dist[cur.to] + next.weight) {
                    dist[next.to] = dist[cur.to] + next.weight;
                    pq.add(new Node(next.to, dist[next.to]));
                }
            }
        }
    }

    public static int stoi(String s) {
        return Integer.parseInt(s);
    }
}

• 플로이드 워셜

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N, M, K;

	static int[][] dist, arr;
	static int[] sum;
	static int MAX = 987654321;

	public static void main(String[] args) throws Exception {
		// input
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int T = stoi(in.readLine());
		for (int tc = 0; tc < T; ++tc) {
			String[] inputs = in.readLine().split(" ");
			N = stoi(inputs[0]);
			M = stoi(inputs[1]);

			dist = new int[N][N];
			for (int i = 0; i < N; ++i) {
				for (int j = 0; j < N; ++j) {
					if (i == j)
						dist[i][j] = 0;
					else
						dist[i][j] = MAX;
				}
			}

			for (int i = 0; i < M; ++i) {
				inputs = in.readLine().split(" ");
				int a = stoi(inputs[0]) - 1;
				int b = stoi(inputs[1]) - 1;
				int c = stoi(inputs[2]);
				dist[a][b] = c;
				dist[b][a] = c;
			}

			floydwarshall();

			K = stoi(in.readLine());
			inputs = in.readLine().split(" ");
			sum = new int[N];
			for (int i = 0; i < K; ++i) {
				int value = stoi(inputs[i]) - 1;
				for (int j = 0; j < N; ++j) {
					sum[j] += dist[value][j];
				}
			}

			int idx = -1;
			int min = MAX;
			for (int i = 0; i < N; ++i) {
				if (sum[i] < min) {
					idx = i + 1;
					min = sum[i];
				}
			}
			sb.append(idx).append("\n");
		}
		System.out.println(sb);
	}

	private static void floydwarshall() {
		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]);
				}
			}
		}
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}