최단 경로 알고리즘 - 연습 문제

문제1)

// Practice1
// 2차원 배열 data 에 그래프 데이터가 주어졌다.
// 무방향이고 간선에 가중치 값이 있는 그래프이다.
// 1번 정점에서 N 번 정점으로 최단 경로로 이동하려고 하는데,
// 두 정점을 경유해서 가려고 한다.
// 1번 점점에서 출발하여 두 정점을 경유하여 N 번 정점으로 가는 최단 경로를 구하세요.

// 입출력 예시)
// 입력 data: {{1, 2, 3}, {1, 3, 5}, {1, 4, 4}, {2, 3, 3}, {2, 4, 5}, {3, 4, 1}}
// 출력: 7

import java.util.ArrayList;
import java.util.PriorityQueue;

public class Practice1 {
    static ArrayList<ArrayList<Node>> graph;
    final static int INF = 1000000000;

    static class Node {
        int to;
        int weight;

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

    public static int solution(int[][] data, int v, int via1, int via2, int start, int n) {
        int case1 = 0;
        int case2 = 0;

        // 그래프 구성
        graph = new ArrayList<>();
        for (int i = 0; i < v + 1; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < data.length; i++) {
            graph.get(data[i][0]).add(new Node(data[i][1], data[i][2]));
        }

        // Case1: start -> via1 -> via2 - > n
        case1 += dijkstra(v, start, via1);
        case1 += dijkstra(v, via1, via2);
        case1 += dijkstra(v, via2, n);

        // Case2: start -> via2 -> via1 -> n
        case2 += dijkstra(v, start, via2);
        case2 += dijkstra(v, via2, via1);
        case2 += dijkstra(v, via1, n);

        // 해당 경로가 없는 경우는 -1
        // 있는 경우는 작은 값 반환
        if(case1 >= INF && case2 >= INF) {
            return -1;
        } else {
            return Math.min(case1, case2);
        }
    }

    public static int dijkstra(int v, int start, int end) {
        PriorityQueue<Node> pq = new PriorityQueue<>((x, y) -> x.weight - y.weight);
        pq.offer(new Node(start, 0));

        // 최단거리 dp 메모리
        int[] dist = new int[v + 1];
        for (int i = 0; i < v + 1; i++) {
            dist[i] = INF;
        }
        dist[start] = 0;

        // 방문 배열
        boolean[] visited = new boolean[v + 1];

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

            // 방문 배열 추가
            if (visited[curNode.to]) {
                continue;
            }
            visited[curNode.to] = true;

            for (int i = 0; i < graph.get(curNode.to).size(); i++) {
                Node adjNode = graph.get(curNode.to).get(i);

                // 방문 배열 체크 추가
                if (!visited[adjNode.to] && dist[adjNode.to] > curNode.weight + adjNode.weight) {
                    dist[adjNode.to] = curNode.weight + adjNode.weight;
                    pq.offer(new Node(adjNode.to, dist[adjNode.to]));
                }
            }
        }
        return dist[end];
    }

    public static void main(String[] args) {
        // Test code
        int[][] data = {{1, 2, 3}, {1, 3, 5}, {1, 4, 4}, {2, 3, 3}, {2, 4, 5}, {3, 4, 1}};
        int v = 4;
        int via1 = 2;
        int via2 = 3;
        int start = 1;
        int n = 4;
        System.out.println(solution(data, v, via1, via2, start, n));
    }
}

7

---

문제2)

// Practice2
// N 개의 우주가 있고, N 개의 우주 사이에 M 개의 포탈과 W 개의 웜홀이 있다.
// 각 포탈에는 시간 비용이 있고, 포탈을 통해 우주를 이동했을 때 시간이 흘러 있다.
// 웜홀에도 시간 비용이 있는데, 웜홀을 통해 우주를 이동하는 경우는 시간이 거꾸로 흘러 있다.
// N 개의 우주를 포탈과 웜홀을 통해 이동 한다고 했을 때,
// 출발 했을 때보다 시간이 거꾸로 흘러가 있는 경우가 있는지 판별하는 프로그램을 작성하세요.

// 흘러가 있는 경우가 없으면 false, 있으면 true 를 출력하세요.

// 입출력 예시)
// 입력:
// n: 3 / m: 3 / w: 1
// portal: {{1, 2, 2}, {1, 3, 4}, {2, 3, 1}}
// wormhole: {{3, 1, 3}}

// 출력: false

public class Practice2 {
    static class Edge {
        int from;
        int to;
        int weight;

        public Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

    final static int INF = 1000000000;
    static Edge[] edge;
    static int[] dist;

    public static void solution(int n, int m, int w, int[][] portal, int[][] wormhole) {
        // 간선 구성
        edge = new Edge[m + w];
        for (int i = 0; i < m; i++) {
            edge[i] = new Edge(portal[i][0], portal[i][1], portal[i][2]);
        }

        // 웜홀은 음수로 가중치 변경해서 추가
        for (int i = 0; i < w; i++) {
            // m + i 로 실수 no! => 앞쪽에 m (포탈)이 들어가 있기 때문
            edge[m + i] = new Edge(wormhole[i][0], wormhole[i][1], -wormhole[i][2]); // 웜홀은 -(음수)로 넣어줌
        }

        // 최단 경로 배열 초기화
        dist = new int[n + 1];
        for (int i = 1; i < n + 1; i++) {
            dist[i] = INF;
        }
        dist[1] = 0;
        System.out.println(bellmanFord(n, m + w));
    }

    public static boolean bellmanFord(int v, int e) {
        boolean isMinusCycle = false;
        for (int i = 0; i < v + 1; i++) {
            for (int j = 0; j < e; j++) {
                Edge cur = edge[j];

                if (dist[cur.from] == Integer.MAX_VALUE) {
                    continue;
                }

                if (dist[cur.to] > (dist[cur.from] + cur.weight)) {
                    dist[cur.to] = dist[cur.from] + cur.weight;

                    if (i == v) {
                        isMinusCycle = true;
                    }
                }
            }
        }
        return isMinusCycle;
    }

    public static void main(String[] args) {
        // Test code
        int n = 3;
        int m = 3;
        int w = 1;
        int[][] portal = {{1, 2, 2}, {1, 3, 4}, {2, 3, 1}};
        int[][] wormhole = {{3, 1, 3}};

        solution(n, m, w, portal, wormhole);  // false

        n = 3;
        m = 2;
        w = 1;
        portal = new int[][] {{1, 2, 3}, {2, 3, 4}};
        wormhole = new int[][] {{3, 1, 8}};
        solution(n, m, w, portal, wormhole);  // true
    }
}

false
true

---

문제3)

// Practice3
// n 개의 도시와, 한 도시에서 출발하여 다른 도시에 도착하는 m 개의 버스가 있다.
// 각 버스는 한 번 사용할 때 필요한 비용이 있다.
// 모든 도시의 쌍 (A, B) 에 대해서 도시 A 에서 B 로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

// 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.
// 갈수 없는 경로는 0을 출력하세요.

// 입출력 예시)
// 입력 busInfo: {{1, 2, 2}, {1, 3, 3}, {1, 4, 1}, {1, 5, 10}, {2, 4, 2}, {3, 4, 1}, {3, 5, 1},
//              {4, 5, 3}, {3, 5, 10}, {3, 1, 8}, {1, 4, 2}, {5, 1, 7}, {3, 4, 2}, {5, 2, 4}}
// 출력:
//    0     2     3     1     4
//   12     0    15     2     5
//    8     5     0     1     1
//   10     7    13     0     3
//    7     4    10     6     0

public class Practice3 {

    static int[][] dist;
    static final int INF = 1000000000;

    public static void solution(int city, int bus, int[][] busInfo) {
        // 최단 경로 인접 행렬 초기화
        dist = new int[city + 1][city + 1];
        for (int i = 1; i < city + 1; i++) {
            for (int j = 1; j < city + 1; j++) {
                if (i != j) {
                    dist[i][j] = INF;
                }
            }
        }

        // 그래프 구성
        // 노선이 하나가 아니므로 최소 비용 경로로 구성
        for (int i = 0; i < bus; i++) {
            dist[busInfo[i][0]][busInfo[i][1]] = Math.min(dist[busInfo[i][0]][busInfo[i][1]], busInfo[i][2]);
        }

        floydWarshall(city);

        // 출력
        for (int i = 1; i < city + 1; i++) {
            for (int j = 1; j < city + 1; j++) {
                if (dist[i][j] >= INF) {
                    System.out.printf("%5d ", 0);
                } else {
                    System.out.printf("%5d ", dist[i][j]);
                }
            }
            System.out.println();
        }
    }

    public static void floydWarshall(int v) {
        for (int k = 1; k < v + 1; k++) {
            for (int i = 1; i < v + 1; i++) {
                for (int j = 1; j < v + 1; j++) {
                    if (dist[i][k] != INF && dist[k][j] != INF) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        // Test code
        int city = 5;
        int bus = 14;
        int[][] busInfo = {{1, 2, 2}, {1, 3, 3}, {1, 4, 1}, {1, 5, 10}, {2, 4, 2}, {3, 4, 1}, {3, 5, 1},
                {4, 5, 3}, {3, 5, 10}, {3, 1, 8}, {1, 4, 2}, {5, 1, 7}, {3, 4, 2}, {5, 2, 4}};
        solution(city, bus, busInfo);
    }
}

 0     2     3     1     4
12     0    15     2     5
 8     5     0     1     1
10     7    13     0     3
 7     4    10     6     0