[Boj_18352] 특정 거리의 도시 찾기

📎 문제 링크

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

18352번: 특정 거리의 도시 찾기

 

▸ 문제

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.

이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

 

 

이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다.  2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.

 

▸ 입력

첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 공백을 기준으로 구분되어 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미다. (1 ≤ A, B ≤ N) 단, A와 B는 서로 다른 자연수이다.

 

▸ 출력

X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력한다.

이 때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.

 

📍 문제 정보

• 🥈 문제 레벨 : 실버 2
• 🔔  문제 유형 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 데이크스트라, 최단 경로
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

• 각 노드에 연결된 [정점, 비용]을 저장할 인접리스트와 시작점에서 각 정점으로 가는 최단거리를 저장할 dist 배열을 만들어주었다.
• 시작점부터 연결된 정점들을 방문하며, 도착지로 가는 가중치가 더 작은 값이 있다면 갱신해 주었다.
• 출발지에서 갈 수 있는 모든 도시 중 dist 배열에 저장된 최단거리와 k가 같은 도시의 번호를 출력해 주었다.

 

🔍 최단 거리 알고리즘

• 그래프에서 정점 간 최단 거리를 구하기 위한 알고리즘으로,
• 다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-워셜 알고리즘이 있다.
• 다익스트라 알고리즘과 벨만-포드 알고리즘은 특정 정점에서 다른 정점까지의 최단 거리를 구하고,
• 플로이드-워셜 알고리즘은 모든 정점 간 최단 거리를 구한다.

 

🔍  다익스트라(Dijkstra)란 ?

• 간선의 가중치가 음수가 아닌 경우 특정 정점에서 다른 정점까지의 최단 거리를 구하는 알고리즘이다.
• 시작 정점을 설정하고, 방문 가능하면서 비용이 가장 적게 드는 정점에 방문해 비용을 갱신한다.
• 이때 각 정점의 비용에 우선순위 큐를 사용하면 시간 복잡도 면에서 효율적일 수 있다.

 

🔸 다익스트라  동작 과정

• 초기에 시작 정점에서 방문 가능한 정점에 대한 비용을 갱신하고, 나머지 정점에 대한 비용은 무한대로 설정한다.
• 방문하지 않은 정점 중 비용이 가장 적게 드는 정점에 방문한다.
  • 해당 정점과 연결된 다른 정점의 비용을 갱신해야 하는지 확인한다.
  • 만약, 해당 정점에 거쳐 다른 정점에 방문할 때 기존보다 적은 비용이 든다면 비용을 갱신한다.
• 모든 정점을 방문할 때까지, 이와 같은 방식으로 정점 방문 비용을 갱신한다.

 

벨만-포드(Bellman-Ford) 알고리즘은 간선의 가중치가 음수인 경우에도 적용할 수 있다. 하지만 음의 사이클이 있다면 최소 비용이 무한하게 줄어들어 알고리즘에 적용할 수 없다.

 

	다익스트라	벨만-포드
음의 가중치	X	O
음의 사이클	X	X
시간 복잡도	O(mlog n)	O(mn)

 

✔ 최종 코드

메모리 : 346656KB
시간 : 1436ms

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int n, m, k, x;
    static ArrayList<ArrayList<pos>> list;
    static int[] dist;
    static boolean[] checked;
    static public class pos implements Comparable<pos>{
        int end; int dist;

        public pos (int end, int dist) {
            this.end = end;
            this.dist = dist;
        }

        @Override
        public int compareTo(pos o) {
            return this.dist - o.dist;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); // 도시의 개수
        m = Integer.parseInt(st.nextToken()); // 도로의 개수
        k = Integer.parseInt(st.nextToken()); // 거리의 정보
        x = Integer.parseInt(st.nextToken()); // 출발 도시의 번호

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

        dist = new int[n+1];
        Arrays.fill(dist, Integer.MAX_VALUE);

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

            list.get(a).add(new pos(b, 1));
        }

        dijkstra(x);

        for (int i = 1; i < dist.length; i++) {
            if (dist[i] == k) {
                sb.append(i).append("\n");
            }
        }

        if (sb.length() == 0) sb.append(-1).append("\n");

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

    private static void dijkstra(int start) {
        PriorityQueue<pos> pq = new PriorityQueue<>();
        checked = new boolean[n+1];
        pq.offer(new pos(start, 0));
        dist[start] = 0;

        while (!pq.isEmpty()) {
            pos now = pq.poll();
            int num = now.end;
            checked[num] = true;

            for (pos next : list.get(num)) {
                if (!checked[next.end] && dist[next.end] > dist[num] + next.dist) {
                    dist[next.end] = dist[num] + next.dist;
                    pq.offer(new pos(next.end, dist[next.end]));
                }
            }
        }
    }
}

 

 

📍 함께 풀어보면 좋은 백준 문제

• 최단경로
• 특정한 최단 경로
• 지름길