[백준] 13424번 : 비밀 모임

13424번: 비밀 모임

---

[Floyd-Warshall or 다익스트라]

나는 플로이드-와샬로 풀었으나, 다익스트라로 푸는 것이 어쩌면 더 적은 시간이 들지도 모르겠다. 다익스트라를 사용한다면 k번의 다익스트라를 수행하게 되니까 말이다.

 

일반적인 플로이드 와샬 문제처럼 거리의 대한 배열 dist를 i == j일때는 0으로, 아닐때는 INF로 초기화 해놓고, 입력에 따라 dist에 값을 대입한다.

            for(int i=1; i<=n; i++)
                for(int j=1; j<=n; j++)
                    dist[i][j] = (i != j)? INF:0;

            for(int i=0; i<m; i++){
                st = new StringTokenizer(br.readLine());

                int h = Integer.parseInt(st.nextToken());
                int tg = Integer.parseInt(st.nextToken());
                int d = Integer.parseInt(st.nextToken());

                dist[h][tg] = d;
                dist[tg][h] = d;
            }

이후 바로 플로이드-와샬

            for(int z=1; z<=n; z++)
                for(int i=1; i<=n; i++)
                    for(int j=1; j<=n; j++)
                    
                        if(i == j)
                            continue;
                        else
                            dist[i][j] = Math.min(dist[i][j], dist[i][z] + dist[z][j]);

나는 친구들이 있는 방을 arr[ ] 배열에 저장해두었다. 즉 arr[0], arr[1], arr[2], ..., arr[k-1]에는 친구들이 있는 방 번호가 저장되어있다. 이 방들을 시작점으로, 1번 방 ~ n번 방으로의 거리를 더해 그 중 가장 작은 값을 갖는 방에서 모이기로 하면 되겠다.

# Code </>

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

public class Main {

    static final int INF = 1000000000;
    static int[][] dist = new int[101][101];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        for(int a=0; a<t; a++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            for(int i=1; i<=n; i++)
                for(int j=1; j<=n; j++)
                    dist[i][j] = (i != j)? INF:0;

            for(int i=0; i<m; i++){
                st = new StringTokenizer(br.readLine());

                int h = Integer.parseInt(st.nextToken());
                int tg = Integer.parseInt(st.nextToken());
                int d = Integer.parseInt(st.nextToken());

                dist[h][tg] = d;
                dist[tg][h] = d;
            }
            int k = Integer.parseInt(br.readLine());

            int[] arr = new int[n];
            st = new StringTokenizer(br.readLine());
            for(int i=0; i<k; i++)
                arr[i] = Integer.parseInt(st.nextToken());

            for(int z=1; z<=n; z++)
                for(int i=1; i<=n; i++)
                    for(int j=1; j<=n; j++)
                        if(i == j)
                            continue;
                        else
                            dist[i][j] = Math.min(dist[i][j], dist[i][z] + dist[z][j]);
            //출력
            int min = INF, idx = -1;
            for(int i=1; i<=n; i++){
            
                int sum = 0;
                
                for(int j=0; j<k; j++)
                    sum += dist[arr[j]][i];

                if(sum < min){
                    idx = i;
                    min = sum;
                }
            }
            System.out.println(idx);
        }
    }
}