본문 바로가기
Hub Algorithm/다익스트라

[BOJ] 백준 13424 : 비밀 모임 (java)

소란스러운 2024. 4. 15.
728x90

🧪 1753 최단경로

난이도 : 🌟 골드 4
유형 : 다익스트라 알고리즘

 

13424번: 비밀 모임

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방

www.acmicpc.net

 

📝 문제

해리와 친구들은 엄브릿지의 감시를 피해 어둠의 마법 방어술을 연습하기 위한 비밀 모임을 하려고 한다. 그들은 아무도 모르게 모임의 장소를 전달하기 위해 가짜 갈레온을 사용하는데, 해리가 자신의 가짜 갈레온에 모임의 장소를 적으면 친구들이 가진 가짜 갈레온에 해리가 적은 장소가 나타난다. 해리가 다니고 있는 호그와트 마법 학교에는 모임에 사용할만한 N개의 방이 있다. 각 방에는 1부터 N까지 번호가 붙어 있으며 중복된 번호는 없다. 마법 학교답게 N개의 방은 M개의 마법으로 만들어진 비밀통로로 연결되어있다. 모든 비밀통로는 양방향 통행이 가능하며 자연수의 길이를 가진다. 모임에 참여하는 친구들은 총 K명이다.

해리는 N개의 방 중에서 한 곳을 정해 오늘 모임의 장소로 이용하려고 한다. 모임 장소를 정하기 전, 호그와트 비밀지도를 이용해 학교 안에 있는 사람들의 현재 위치를 확인해보니 모임에 참여하는 친구들은 N개의 방 중에서 한군데씩에 각각 위치해 있었다. 불행하게도 호그와트 안에서는 순간이동이 금지되어 있어서 모임에 참여하는 친구들은 들키지 않도록 비밀통로만 이용해서 오늘의 모임 장소로 가려고 한다. 이때 이들은 항상 처음 위치에서 모임 장소까지의 이동 거리가 가장 짧은 경로만을 이용한다. 여기서 ‘이동 거리’란 처음 위치에서 모임 장소까지 가기 위해 이용한 비밀 통로들의 길이의 합을 의미한다. 어느 방을 모임 장소로 사용할까 고민하던 해리는 모임에 참석하는 친구들의 이동 거리의 총합이 최소가 되는 방을 오늘의 모임 장소로 사용하기로 했다. 다음 그림은 N = 6, M = 7, K = 2인 경우의 예시이다.

위 그래프에서 각 정점에 적힌 숫자는 방의 번호이며, 간선 위의 숫자는 방과 방을 연결하는 비밀통로의 길이이다. 모임에 참석하는 두 친구는 현재 3번, 5번 방에 있다. 만약 오늘 모임의 장소로 2번 방을 이용한다면 3번 방에 있는 친구 A의 가장 짧은 경로는 3번-2번 방 순이며 이동 거리는 2가 된다. 5번 방에 있는 친구 B의 경우 2번 방으로 가는 가장 짧은 경로는 5번-1번-3번-2번 방 순이며 이동 거리는 5가 된다. 이때, 두 친구의 이동 거리의 총합은 7이 된다. 그러나 만약 1번 방을 모임 장소로 선택한다면, 친구 A의 이동 거리는 1이 되며, 친구 B의 이동 거리는 2가 되어, 두 친구의 이동 거리의 총합은 3이 된다. 위 예시에서는 1번, 3번, 또는 5번 방을 오늘 모임의 장소로 이용했을 때 친구들의 이동 거리의 총합이 3으로 최소가 된다.

해리가 오늘의 모임 장소를 가짜 갈레온에 적으면 모임에 참여하는 K명의 친구는 그 사실을 즉시 알게 되며, 현재 하던 일을 모두 중단하고, 바로 오늘의 모임 장소로 이동한다. 해리를 위해 친구들의 이동 거리의 총합이 최소가 되도록 하는 모임 장소를 찾아 출력하는 프로그램을 작성하시오.

 

입력

 

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방의 개수 N (2 ≤ N ≤ 100), 비밀통로의 개수 M(N-1 ≤ M ≤ N(N - 1)/2)이 공백으로 구분되어 주어진다. 그 다음 줄부터 M개의 줄에 걸쳐 비밀통로의 정보(a, b, c)가 주어진다. a와 b는 비밀통로로 연결된 두 방의 번호이며 c는 a와 b를 연결하는 비밀통로의 길이이다. a와 b는 항상 다르며 c는 1 이상 1,000 이하의 자연수이다. 두 방을 연결하는 비밀통로는 반드시 하나씩만 존재한다. 또한 어떤 방에서 다른 방으로 비밀통로를 이용해서 갈 수 없는 경우는 존재하지 않으며, 같은 비밀통로에 대한 정보가 중복되어 주어지지 않는다. 비밀통로의 정보가 모두 주어진 다음 그 다음 줄에 모임에 참여하는 친구의 수 K(1 ≤ K ≤ N)가 주어진다. 각 테스트 케이스의 마지막 줄에는 모임에 참여하는 친구들이 현재 위치해 있는 방의 번호 K개가 공백으로 구분되어 주어진다. 친구들이 있는 방은 항상 N개의 방 중 하나이며, 방 번호가 중복되는 경우는 없다. 즉, 두 명 이상이 한 방에 있는 경우는 입력으로 주어지지 않는다. 

 

출력

 

출력은 표준 출력을 사용한다. 입력받은 데이터에 대해, 각 테스트 케이스의 답을 순서대로 1줄에 1개씩 출력한다. 각 테스트 케이스마다 모임에 참여하는 친구들의 이동 거리의 총합이 최소가 되도록 하는 모임 장소의 방 번호를 출력한다. 만약 그러한 장소가 여러 개일 경우, 그중 번호가 가장 작은 방의 번호를 출력한다.

 

🚧  1) 다익스트라로 푸는 방법

🧐 핵심 로직

  1. 인접리스트를 활용해서 입력값을 graph에 채워준다.
  2. 친구 수 만큼 반복을 통해서 다익스트라 메서드에 시작 노드를 넣는다.
  3. 다익스트라 메서드 내부에서는 거리 배열과 방문 배열을 초기화 해주고 이때, 거리 배열은 시작 노드 제외 INF값으로 초기화 해줌으로써 최소 거리로 갱신할 수 있도록 한다.
  4. 우선순위큐를 활용해서 최소의 비용을 가진 노드가 먼저 들어가도록 한 후 Queue에 넣는 과정을 반복한다.
  5. 각 노드가 끝날때마다 거리 배열의 값을 정답 배열에 넣어둔다.
  6. 정답배열에서 이동거리의 총합이 최소가 되는 노드 번호를 출력해준다.

💻 최종 코드 (656 ms)

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

public class Main {

    static class Node implements Comparable<Node> {

        int to, cost;

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

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

    static int INF = 987654321;
    static int v, e;
    static int[] dist, ans;
    static boolean[] visited;
    static List<List<Node>> graph;
    public static void main(String[] args) throws IOException {

        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));
        StringBuilder sb = new StringBuilder();

        int t = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= t; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            v = Integer.parseInt(st.nextToken());
            e = Integer.parseInt(st.nextToken());

            graph = new ArrayList<>();
            for (int i = 0; i <= v; i++) {
                graph.add(new ArrayList<>());
            }

            for (int i = 1; i <= e; i++) {
                st = new StringTokenizer(br.readLine());
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());
                int cost = Integer.parseInt(st.nextToken());

                graph.get(from).add(new Node(to, cost));
                graph.get(to).add(new Node(from, cost));
            }

            int k = Integer.parseInt(br.readLine());
            ans = new int[v + 1];

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < k; i++) {
                int startV = Integer.parseInt(st.nextToken());
                dijkstra(startV);

                for (int j = 1; j <= v; j++) {
                    ans[j] += dist[j];
                }
            }

            int result = Integer.MAX_VALUE;
            int res = 0;
            for (int i = 1; i <= v; i++) {
                if (ans[i] < result) {
                    result = ans[i];
                    res = i;
                }
            }

            sb.append(res).append("\n");
        }

        System.out.println(sb);
        br.close();
    }

    private static void dijkstra(int curNode) {

        dist = new int[v + 1];
        Arrays.fill(dist, INF);
        visited = new boolean[v + 1];

        PriorityQueue<Node> q = new PriorityQueue<>();
        q.add(new Node(curNode, 0));
        dist[curNode] = 0;

        while (!q.isEmpty()) {
            Node now = q.poll();
            visited[now.to] = true;

            for (Node next : graph.get(now.to)) {

                if (!visited[next.to] && dist[next.to] > dist[now.to] + next.cost) {
                    dist[next.to] = dist[now.to] + next.cost;
                    q.add(new Node(next.to, dist[next.to]));
                }
            }
        }
    }
}

 

🚧  2) 플로이드 - 워셜 로 푸는 방법

🧐 핵심 로직

  • 다익스트라와 전체적인 틀은 비슷하지만 중간에 플로이드 - 워셜 방식으로 모든 정점쌍 간의 최단경로를 구하면 된다.

💻 최종 코드 (448 ms)

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

public class Main {

    static int INF = 987654321;
    static int v, e;
    static int[][] dist;
    static List<List<Integer>> graph;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int t = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= t; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            v = Integer.parseInt(st.nextToken());
            e = Integer.parseInt(st.nextToken());

            dist = new int[v + 1][v + 1];
            for (int i = 1; i <= v; i++) {
                Arrays.fill(dist[i], INF);
                dist[i][i] = 0;
            }

            graph = new ArrayList<>();
            for (int i = 0; i <= v; i++) {
                graph.add(new ArrayList<>());
            }

            for (int i = 1; i <= e; i++) {
                st = new StringTokenizer(br.readLine());
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());
                int cost = Integer.parseInt(st.nextToken());

                graph.get(from).add(to);
                graph.get(to).add(from);
                dist[from][to] = cost;
                dist[to][from] = cost;
            }

            for (int k = 1; k <= v; k++) {
                for (int i = 1; i <= v; i++) {
                    for (int j = 1; j <= v; j++) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }

            int k = Integer.parseInt(br.readLine());
            int[] ans = new int[v + 1];

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < k; i++) {
                int startV = Integer.parseInt(st.nextToken());

                for (int j = 1; j <= v; j++) {
                    ans[j] += dist[startV][j];
                }
            }

            int result = Integer.MAX_VALUE;
            int res = 0;
            for (int i = 1; i <= v; i++) {
                if (ans[i] < result) {
                    result = ans[i];
                    res = i;
                }
            }

            sb.append(res).append("\n");
        }

        System.out.println(sb);
        br.close();
    }
}
 
저작자표시 비영리 변경금지

'Hub Algorithm > 다익스트라' 카테고리의 다른 글

[BOJ] 백준 2307 : 도로검문 (java)  (0) 2024.09.10
[BOJ] 백준 1261 : 알고스팟 (java)  (0) 2024.06.12
[BOJ] 백준 12834 : 주간 미팅 (java)  (0) 2024.06.01
[BOJ] 백준 1753 : 최단경로 (java)  (2) 2024.03.16

'Hub Algorithm/다익스트라' 관련글

티스토리툴바