백준/11404 플로이드 / (최단경로찾기) 플로이드 와샬,다익스트라

플로이드

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

48443

20032

14176

41.698%

문제

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

출력

n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

예제 입력 1 복사

5
14
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

예제 출력 1 복사

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

---

풀이

최단비용을 찾는 문제 

최단비용을 구할 수 있는 BFS는 간선의 가중치가 같아야하고,

다익스트라는 간선의 가중치가 달라도 음수의 가중치가 없어야하고

벨만 포드는 음수 가중치가 있어도 된다.

이 문제는 음수의 가중치가 없으므로 다익스트라를 사용한다.

 

다익스트라는 하나의 정점에서 다른정점까지의 최소비용을 구한다.

이문제는 "모든정점"에서 다른 "모든정점"까지의 최소비용을 원한다. 이때는 플로이드 와샬을 사용한다고한다.

 

비용의 최대값을 생각해서 비용을 저장하는 배열을 long으로 선언했다.

출력할때 초기화한값이 그대로인경우는 갈 수 없다는것을 의미하므로 그것까지 체크해서 0을 출력해준다.

 

아래코드는 다익스트라를 사용한 코드.  두 정점끼리 경로가 여러개인데도 불구하고 잘 동작하였다.

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int v, e;
    static long[] cost; // 10만개 간선 * 10만의 비용 => 최대 비용 10만^2이므로 long
    static List<List<Node>> graph;
    static final int maxRange = 100000 * 100000;


    /*
    최단비용 해결문제이다. 가중치가 서로 다르고, 양수이므로 다익스트라를 사용한다.
     */

    public static void main(String[] args) throws IOException {
        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {
        v = Integer.parseInt(br.readLine());
        e = Integer.parseInt(br.readLine());
        cost = new long[v+1];
        Arrays.fill(cost, maxRange + 1);
        graph = new ArrayList<>();
        for (int i = 0; i < v + 1; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < e; i++) {
            int[] edgeInfo = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt)
                .toArray();
            graph.get(edgeInfo[0]).add(new Node(edgeInfo[1], edgeInfo[2]));
        }


    }

    static void solve() throws IOException {
        for (int i = 1; i <= v; i++) {
            dijkstra(i);
            for (int j = 1; j <= v; j++) {
                if (i == j || cost[j] == maxRange+1) {
                    bw.write(0 + " ");
                } else {
                    bw.write(cost[j]+" ");
                }
            }
            bw.newLine();
            Arrays.fill(cost,maxRange+1);
        }

    }

    static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> (int) (o1.cost - o2.cost));
        cost[start] = 0;
        pq.add(new Node(start, 0));

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

            if (cost[pqNode.index] < pqNode.cost) {
                continue;
            }

            for (Node adjNode : graph.get(pqNode.index)) {
                if (cost[adjNode.index] > cost[pqNode.index] + adjNode.cost) {
                    cost[adjNode.index] = cost[pqNode.index] + adjNode.cost;
                    pq.add(new Node(adjNode.index, cost[adjNode.index]));
                }
            }

        }

    }


    static class Node {

        int index;
        long cost;

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


}

 

플로이드 워셜 사용

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int v, e;
    static long[][] cost;
    static final long maxRange = 100000L * 100000;
    /*
     */

    public static void main(String[] args) throws IOException {
        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {
        v = Integer.parseInt(br.readLine());
        e = Integer.parseInt(br.readLine());
        cost =new long[v+1][v+1];
        //인접행렬 초기화
        for (int i = 1; i <= v; i++) {
            for (int j = 1; j <= v; j++) {
                if (i == j) {
                    cost[i][j] = 0;
                } else {
                    cost[i][j] = maxRange + 1; //최대값으로 초기화
                }
            }
        }
        //입력된 간선 정보를 이용하여 인접행렬 초기화
        for (int i = 0; i < e; i++) {
            int[] edgeInfo = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt)
                .toArray();
            //두 정점사이에 많은 간선이 있을 수 있다. 그러면 들어오는 간선 정보중 가장 작은값을 인접행렬에 저장하기 위함.
            cost[edgeInfo[0]][edgeInfo[1]] = Math.min(cost[edgeInfo[0]][edgeInfo[1]], edgeInfo[2]);
        }

    }

    static void solve() throws IOException {
        floyd();
        for (int i = 1; i <= v; i++) {
            for (int j = 1; j <= v; j++) {
                if (cost[i][j] == maxRange + 1) {
                    bw.write(0 + " ");
                } else {
                    bw.write(cost[i][j]+" ");
                }
            }
            bw.newLine();
        }

    }

    static void floyd() {
        //각각 모든 정점을 경유해서 가는 경우를 생각해본다.
        for (int i = 1; i <= v; i++) {
            // j->k를 갈때 cost[j][k]의 비용이 더 작을지 아니면 j->i  i->k 처럼 i 노드를 경유해서 가는것이 더 비용이 적은지 체크하고, 갱신해준다.
            for (int j = 1; j <= v; j++) {
                for (int k = 1; k <= v; k++) {
                    if (cost[j][k] > cost[j][i] + cost[i][k]) {
                        cost[j][k] = cost[j][i] + cost[i][k];
                    }
                }
            }
        }
    }

}