[백준/Baekjoon] 14938 서강그라운드 C++ :: Floyd-Warshall

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

14938번: 서강그라운드

 

---

1. Logic

- 모든 점에서 모든 점까지의 최단 거리를 각각 구해야한다. >> 플로이드 와샬 알고리즘

플로이드 와샬 알고리즘은 3중 for문을 돌아야하기 때문에 노드의 갯수가 적을 때 사용할 수 있다.

 

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n, m, r;
const int INF = 0x3f3f3f3f;

vector<vector<int>> dist(101, vector<int> (101, INF));
int item[101];

void floyd() {
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(i == j) dist[i][j] = 0;
        }
    }

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n >> m >> r;

    for(int i = 1; i <= n; i++) {
        cin >> item[i];
    }

    for(int i = 0; i < r; i++) {
        int s, e, c;
        cin >> s >> e >> c;
        dist[s][e] = c;
        dist[e][s] = c;
    }

    floyd();

    int ans = 0;

    for(int i = 1; i <= n; i++) {
        int sum = 0;
        for(int j = 0; j <= n; j++) {
            if(dist[i][j] <= m) {
                sum += item[j];
            }
        }
        ans = max(ans, sum);
    }

    cout << ans;
}

 

 

---

 

 

3. Feedback

처음에는 플로이드 와샬 알고리즘이 익숙하지 않아서 모든 노드에서 다익스트라를 돌았지만 어떤 이유에선지 메모리 초과가 떴다. 그래서 구글링을 통해 모든 간선의 최단거리를 구할 수 있는 방법중에 플로이드 와샬이 있다는 것을 알고 공부하고 풀었다. 알고리즘++;

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐