특정 거리의 도시 찾기 - 백준 18352 - Java - 다익스트라

1. 문제

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

 

 

2. 문제풀이 전략

해당 문제는 BFS로도 해결 가능하지만,

가중치가 있는 그래프의 일반적인 경우를 고려하면 다익스트라 알고리즘이 훨씬 더 범용적인 해결책이 된다.

따라서, 다익스트라 알고리즘을 활용해서 이 문제를 풀어보겠다.

 

3. 다익스트라(Dijkstra) 알고리즘이란?

다익스트라(Dijkstra) 알고리즘은 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 특히 음의 가중치가 없는 그래프에서 사용된다. 참고로, 음의 가중치를 가진 간선이 있는 그래프에서 최단 경로를 찾아야 한다면 벨만-포드(Bellman-Ford) 알고리즘을 사용해야 한다.

 

4. 우선순위 큐를 사용 - 시간 복잡도 O(E logV)

E는 간선 개수, V는 정점 개수라고 할 때, 

반복문을 사용해서 최로 거리를 가진 정점을 찾는다면 전체 시간 복잡도가 O(V^2) 된다.

 

우선순위 큐를 사용하면 최소 거리를 가진 정점을 찾는 데 O(logV), 

전체 시간 복잡도는 O(E logV)로 개선된다.

따라서, 우선순위 큐를 사용하는 것이 훨씬 효율적인 방법이다.

 

5. 풀이

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

/**
 * 특정 거리의 도시 찾기 - 백준 18352
 * https://www.acmicpc.net/problem/18352
 * BFS, 다익스트라
 * */
public class FindingCity10 {

    private static int N; // 도시의 개수
    private static int M; // 도로의 개수
    private static int K; // 거리 정보
    private static int X; // 출발 도시 번호
    private static int[] distances; // 출발도시인 x와의 최단경로
    private static ArrayList<Edge>[] edgeList; // 도시 인접리스트

    private static void dijkstra() {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(X, 0));
        while (!pq.isEmpty()) {
            Edge edge = pq.poll();
            int vertex = edge.getVertex();
            int cost = edge.getCost();
            // 최적화 로직 - 이미 처리된 정점에 대한 불필요한 탐색 방지
            if (distances[vertex] < cost) {
                continue;
            }
            // 해당 도시와 연결되어 있는 도시들 탐색
            for(int i = 0; i < edgeList[vertex].size(); i++) {
                int vertex2 = edgeList[vertex].get(i).getVertex();
                int cost2 = edgeList[vertex].get(i).getCost() + cost;
                // 최단 경로 갱신
                if (distances[vertex2] > cost2) {
                   distances[vertex2] = cost2;
                   pq.add(new Edge(vertex2, cost2));
                }
            }

        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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());
        // 생성 초기화
        distances = new int[N + 1];
        edgeList = new ArrayList[N + 1];
        Arrays.fill(distances, Integer.MAX_VALUE);
        for (int i = 1; i <= N; i++) {
            edgeList[i] = new ArrayList<>();
        }
        // 경로 초기화
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            // A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재
            edgeList[start].add(new Edge(end, 1));
        }
        // 출발 도시
        distances[X] = 0;
        // 다익스트라
        dijkstra();
        StringBuilder sb = new StringBuilder();
        int answer = 0;
        for (int i = 1; i < distances.length; i++) {
            int distance = distances[i];
            if (distance == K) {
                sb.append(i).append("\n");
                answer++;
            }
        }
        if (answer == 0) {
            bw.write("-1");
        } else {
            bw.write(sb.toString());
        }

        bw.flush();
        bw.close();
        br.close();
    }

    private static class Edge implements Comparable<Edge> {
        int vertex;
        int cost;

        public Edge(int vertex, int cost) {
            this.vertex = vertex;
            this.cost = cost;
        }

        public int getVertex() {
            return vertex;
        }

        public int getCost() {
            return cost;
        }

        @Override
        public int compareTo(Edge o) { // 오름차순
            return cost - o.cost;
        }
    }
}

 

 

6. 문제 풀이 분석

6 - 1. 최적화 로직

if (distances[vertex] < cost) {
    continue;
}

• 이미 처리된 정점에 대해 불필요한 탐색을 방지한다.

 

6 - 2. 최단 경로 갱신

if (distances[vertex2] > cost2) {
    distances[vertex2] = cost2;
    pq.add(new Edge(vertex2, cost2));
}

• 더 짧은 경로를 발견하면 거리를 갱신한다.
• 새로운 최단 경로를 우선순위 큐에 추가

 

6 - 3. 우선순위 큐 - 최소 힙

private static class Edge implements Comparable<Edge> {
    int vertex;
    int cost;

    public Edge(int vertex, int cost) {
        this.vertex = vertex;
        this.cost = cost;
    }

    public int getVertex() {
        return vertex;
    }

    public int getCost() {
        return cost;
    }

    @Override
    public int compareTo(Edge o) { // 오름차순
        return cost - o.cost;
    }
}

Comparable 인터페이스를 구현했는데, 

해당 인터페이스를 구현하지 않고 Comparator를 넣어도 된다.

아래 처럼 말이다.

PriorityQueue<Edge> pq = new PriorityQueue<>((o1, o2) -> o1.getCost() - o2.getCost());

 

6 - 3. 다익스트라 표준 구현

private static void dijkstra() {
    PriorityQueue<Edge> pq = new PriorityQueue<>();
    pq.add(new Edge(X, 0));
    while (!pq.isEmpty()) {
        Edge edge = pq.poll();
        int vertex = edge.getVertex();
        int cost = edge.getCost();
        // 최적화 로직 - 이미 처리된 정점에 대한 불필요한 탐색 방지
        if (distances[vertex] < cost) {
            continue;
        }
        // 해당 도시와 연결되어 있는 도시들 탐색
        for(int i = 0; i < edgeList[vertex].size(); i++) {
            int vertex2 = edgeList[vertex].get(i).getVertex();
            int cost2 = edgeList[vertex].get(i).getCost() + cost;
            // 최단 경로 갱신
            if (distances[vertex2] > cost2) {
               distances[vertex2] = cost2;
               pq.add(new Edge(vertex2, cost2));
            }
        }

    }
}

 

References

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

https://youngest-programming.tistory.com/536