[백준] 1504 : 특정한 최단 경로 (+ BFS vs. Dijkstra)

문제 출처 : https://www.acmicpc.net/problem/1504

소요 시간 : 시도(1h 30m, 실패)  + 풀이(20m)

---

문제

---

시도

 

기존에 이미 방문했던 정점도 다시 방문 가능하다는 점에서 플로이드-와샬 알고리즘 써도 풀리지 않을까 싶어 시도해봤다.

 

/*

  원래의 '최단 경로'라면 그냥 BFS로 이동하기 때문에 정점과 간선에 대한 중복을 허용하지 않지만
  이 문제의 경우 반드시 방문해야 하는 특정 정점으로 인해 중복을 허용한다는 점이 가장 중요해보인다.

  BFS를 시도하되, 1번 정점에서 특정 정점에 도착할 때, 중간에 방문해야 하는 특정 정점에 모두 방문했는지 확인한다.
  
  int[][] matrix = new int[N+1][N+1];
*/

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

public class Main {

    private static final int INF = 987654321;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());    // 2 ~ 800
        int E = Integer.parseInt(st.nextToken());    // 0 ~ 200,000

        int[][] matrix = new int[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                matrix[i][j] = INF;
            }

            matrix[i][i] = 0;
        }

        int a, b, c;
        while (E-- > 0) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());

            matrix[a][b] = c;
            matrix[b][a] = c;
        }

        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (matrix[i][j] > matrix[i][k] + matrix[k][j]) {
                        matrix[i][j] = matrix[i][k] + matrix[k][j];
                    }
                }
            }
        }

        st = new StringTokenizer(br.readLine());
        int v1 = Integer.parseInt(st.nextToken());
        int v2 = Integer.parseInt(st.nextToken());

        if (matrix[v1][v2] == INF) {
            System.out.println(-1);
            return;
        }

        int res1 = matrix[1][v1] + matrix[v1][v2] + matrix[v2][N];
        int res2 = matrix[1][v2] + matrix[v2][v1] + matrix[v1][N];
        System.out.println(Math.min(res1, res2));
    }
}

 

 

채점이 75%까지 진행되다가 실패했다...

 

또 무엇을 고려하지 못한 걸까..

---

풀이

 

다른 사람의 풀이를 통해 다익스트라 알고리즘을 활용하는 문제였던 걸 확인했다.

 

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

public class Main {

    private static int INF = 200_000_000;    // 200,000 * 1,000
    private static ArrayList<Node>[] adj;
    private static int[] cost;
    private static boolean[] visited;

    private static class Node implements Comparable<Node> {
        int dest, cost;

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

        @Override
        public int compareTo(Node node) {
            return this.cost - node.cost; // cost 기준 오름차순
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());    // 2 ~ 800
        int M = Integer.parseInt(st.nextToken());    // 0 ~ 200,000

        cost = new int[N + 1];
        visited = new boolean[N + 1];
        adj = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            adj[i] = new ArrayList<>();
        }

        int a, b, c;
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());

            adj[a].add(new Node(b, c));
            adj[b].add(new Node(a, c));
        }

        st = new StringTokenizer(br.readLine());
        int v1 = Integer.parseInt(st.nextToken());
        int v2 = Integer.parseInt(st.nextToken());

        // i) 1 < n1 < n2 < N
        int ans1 = dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, N);

        // ii) 1 < n2 < n1 < N
        int ans2 = dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, N);

        int result = ans1 >= INF && ans2 >= INF ? -1 : Math.min(ans1, ans2);
        System.out.println(result);
    }

    private static int dijkstra(int start, int end) {
        // 최저비용 기준 탐색 경로 저장을 위한 우선순위 큐
        PriorityQueue<Node> pq = new PriorityQueue<>();
        Arrays.fill(visited, false);
        Arrays.fill(cost, INF);

        cost[start] = 0;
        pq.add(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node current = pq.poll();

            if (visited[current.dest]) continue;
            visited[current.dest] = true;

            for (Node next : adj[current.dest]) {
                if (cost[next.dest] > next.cost + current.cost) {
                    cost[next.dest] = next.cost + current.cost;
                    pq.add(new Node(next.dest, cost[next.dest]));
                }
            }
        }

        return cost[end];
    }
}

// 참고 출처 : https://lucysworld.tistory.com/33

 

 

보기에는 BFS 알고리즘과 구조가 다를 것 없다고 생각했는데, 이김에 BFS와 다익스트라가 각각 어떻게 다른지 정리했다.

---

정리

 

※ BFS vs. Dijkstra

	BFS	Dijkstra
목적	그래프와 트리를 레벨 단위로 탐색하며, edge weight를 고려하지 않아 무게 없는 그래프에 주요 사용	무게 그래프에서 단일 정점부터 다른 모든 정점들까지의 최단 경로를 찾기 위해 사용.
최적	정점의 개수에 따라 최단 경로를 찾지만, edge weight 고려 안함	edge weight의 총합에 기반해 최단 경로 탐색
큐 유형	(일반 큐를 통해) 다른 레벨로 이동하기 전에 노드의 모든 이웃을 탐색함	(우선순위 큐를 통해) 최소 거리만으로 경로를 탐색함
적용	그래프 내 연결된 구성요소 탐색 / 이분 점검 / 무게 없는 그래프 탐색	무게 그래프 최소거리 탐색 / 네트워크 라우팅 프로토콜
음의 정수	적합하지 않음	주로 음이 아닌 무게 그래프를 위해 설계됨