[백준] 13424번. 비밀 모임(JAVA)

문제

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

---

풀이(14분)

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

public class Main {

    // N개의 방 1~N번 번호 붙어있음
    // N개의 방은 M개의 통로로 연결 ( 양방향 통로이며 자연수 길이 가짐 )
    // K명이 참여
    // N개의 방중에서 한개씩 각각 위치해있음(K <= N인듯?)
    // 각자 모임 장소까지 최단거리로만 이동함(모든 거리를 찾아야하니 플로이드 워셜일듯?)
    // -> 방 개수가 200이하인지 생각하자.
    // 학생들이 위치한 점을 List로 저장해두고, 그 점에서 도달하는 점들의 거리를 누적합하여 해결하자.
    static int T, N, M;
    static int[][] floyd;
    static final int MAX = 1_000_001;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        T = Integer.parseInt(br.readLine());

        while(T-- > 0){
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            floyd = new int[N+1][N+1]; // 배열 초기화
            for(int i = 0; i < N+1; i++){
                Arrays.fill(floyd[i], MAX); // 초기값 설정
            }
            for(int i = 0; i < N+1; i++){
                floyd[i][i] = 0;
            }

            for(int i = 0; i < M; i++){
                st = new StringTokenizer(br.readLine());
                int first = Integer.parseInt(st.nextToken());
                int second = Integer.parseInt(st.nextToken());
                int length = Integer.parseInt(st.nextToken());
                floyd[first][second] = length;
                floyd[second][first] = length;
            }

            int studentCount = Integer.parseInt(br.readLine()); // 학생의 수
            int[] students = new int[studentCount]; // 학생 위치
            st = new StringTokenizer(br.readLine());
            for(int i = 0; i < studentCount; i++){
                students[i] = Integer.parseInt(st.nextToken());
            }

            floyd();
            int[] sum = new int[N+1];
            for(int i : students){
                for(int j = 1; j <= N; j++){
                    sum[j] += floyd[i][j];
                }
            }
            int min = Integer.MAX_VALUE;
            int answer = 0;
            for(int i = 1; i <= N; i++){
                if(min > sum[i]){
                    min = sum[i];
                    answer = i;
                }
            }
            System.out.println(answer);
        }

    }

    // 플로이드 - 워셜 알고리즘
    static void floyd() {
        // 경유지
        for (int k = 1; k <= N; k++) {
            // 출발지
            for (int i = 1; i <= N; i++) {
                //도착지
                for (int j = 1; j <= N; j++) {
                    floyd[i][j] = Math.min(floyd[i][j], floyd[i][k]+floyd[k][j]);
                }
            }
        }
    }
}

---

문제 풀이 전략

 

문제를 독해하며 최단거리라는 것을 분석해 낼 수 있었다.

 

최단 거리라고 하면 몇 가지 알고리즘을 떠올리고 상황에 맞게 적용하면 된다.

그중에서 모든 정점에 대한 모든 정점의 거리를 알아낼 수 있는 플로이드-워셜 알고리즘을 떠올렸고 적용했다.

 

거리를 전부 구한 뒤에 입력받아두었던 정점들마다 각 정점에 대한 거리를 누적합 하여 해결했다.