BOJ 11404: 플로이드

✔ 문제 링크

BOJ 11404: 플로이드

---

✔ 문제해결전략

• All-Pairs Shortest Path(Floyd)

---

✔ 해결과정

주어진 그래프에서 모든 정점 쌍 사이의 최단거리(All-Pairs Shortest Path)를 구해야 한다. weight가 음수인 경우는 없으므로 문제 제목에 나온 플로이드 알고리즘 사용하면 된다.

시작점과 도착점을 제외한 모든 점을 거치는 경로 + 모든 weight가 max인 100,000일 때 dist가 9,900,000이므로 dist 행렬의 모든 값을 10,000,000로 초기화해두고 a, b, c가 주어지면 dist[a][b]를 업데이트한다. 근데 아무 생각 없이

dist[a][b] = c;

라고 하면 안 된다. 문제 본문을 보면 "시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다." 라고 적혀있다. 따라서 시작, 도착 도시 연결하는 노선이 여러 개일 경우 weight가 최소인 노선을 택해야 하므로 아래와 같이 기존의 dist[a][b]와 새로 주어진 c 중 작은 값으로 dist[a][b]를 업데이트하면 된다.

dist[a][b] = min(dist[a][b], c);

---

✔ 정답 CODE

#include <bits/stdc++.h>
using namespace std;

int dist[101][101];
const int INF = 10000000; // 100000 * 100

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    fill(&dist[0][0], &dist[101-1][101], INF);

    while(m--) {
        int a, b, c;
        cin >> a >> b >> c;
        dist[a][b] = min(dist[a][b], c); // b/c edge between a, b is not unique
    }

    for(int i=1;i<=n;i++) dist[i][i] = 0;

    for(int k=1;k<=n;k++) {
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
            }
        }
    }
    
    


    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            if(dist[i][j] == INF) cout << "0 ";
            else cout << dist[i][j] << ' ';
        }
        cout << '\n';
    }

}

---

✔ Check Point

배열 초기화할 때 아무 생각 없이 memset or std::fill을 사용해왔는데 문득 둘의 차이가 궁금해서 검색해 보았다.

---

✔ memset() vs std::fill()

• memset(): assembler로 작성되어서 속도는 무지 빠름. 1바이트 단위로 메모리를 초기화. So, 0 or false로 초기화 할 때 주로 사용. But, bool형이 아닌 배열을 1로 초기화는 불가능
• std::fill(): 내부적으로 루프문을 수행해서 초기화를 수행
• memset(A, x, sizeof(A))
• fill(start, end +1, x);

---

✔ Comment

int overflow 조심 또 조심.

운 좋게도 여기서는 INF 값을 작게 잡아서 문제없었지만 아무 생각 없이 INF를 Ox7f7f7f7f로 두고 INF+INF 했으면 int overflow 발생했을 것이다.

이 기회에 시프 앞 단원 복습하는 것도 좋을 거 같다