반응형

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

 

11404번: 플로이드

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽어보고 오시는 걸 추천드립니다!!

https://rudalsd.tistory.com/24?category=1064608 

 

플로이드 와샬 알고리즘(Floyd Warshall Algorithm)

오늘 설명할 알고리즘은 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)입니다. 이 알고리즘은 dijkstra와 비슷하게 각 정점까지 가는 최단 거리를 알아낼 수 있습니다. 플로이드 와샬 알고리즘이

rudalsd.tistory.com

 

이번 문제에서는 각 노드까지의 최단거리를 출력하지만 갈 수 없는 곳은 0으로 출력해야 한다는 조건이 있었습니다.

 

따라서 한번도 초기화되지 않았던 노드는 0으로 출력한다는 예외조건만 넣어주면 쉽게 풀 수 있는 문제였습니다.

 

[ 소스 코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
 
using namespace std;
 
int n, m;
long long cost[101][101];
 
int main()
{
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++) {            //출발지와 도착지가 같을 때 0으로 초기화
        for (int j = 1; j <= n; j++) {        //아니라면 INF로 초기화
            if (i == j) {
                cost[i][j] = 0;
            }
            else {
                cost[i][j] = 99999999999;
            }
        }
    }
 
    for (int i = 0; i < m; i++) {            //출발지와 도착지가 같은 간선이 여러개일 때
        int a, b, c;                        //가장 짧은 거리로 초기화
        scanf("%d %d %d", &a, &b, &c);
        if (cost[a][b] > c) {
            cost[a][b] = c;
        }
    }
 
    for (int k = 1; k <= n; k++) {            //거쳐가는 노드
        for (int i = 1; i <= n; i++) {        //출발 노드
            for (int j = 1; j <= n; j++) {    //도착 노드
                if (cost[i][j] > cost[i][k] + cost[k][j]) {
                    cost[i][j] = cost[i][k] + cost[k][j];
                }
            }
        }
    }
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (cost[i][j] == 99999999999) {    //한번도 갱신이 되지 않았다면
                cout << 0 << " ";                //갈 수 없으므로 0출력
            }
            else {
                cout << cost[i][j] << " ";
            }
        }
        cout << endl;
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 2638번 - 치즈 (C++)  (0) 2022.06.13
[ 백준 ] 13460번 - 구슬 탈출 2 (C++)  (0) 2022.06.12
[ 백준 ] 1865번 - 웜홀 (C++)  (0) 2022.06.10
[ 백준 ] 1238번 - 파티 (C++)  (0) 2022.06.09
[ 백준 ] 12865번 - 평범한 배낭 (C++)  (0) 2022.06.08

+ Recent posts

티스토리툴바