[플로이드-워셜(Floyd-Warshall)] - BOJ_14938 : 서강그라운드

오늘은 오랜만에 그래프 알고리즘을 공부하려고 한다.

블로그에 글은 안썼지만, 그동안 프림, 크루스칼등 MST(최소 신장 트리) 그리고 다익스트라(한 정점에서 다른 정점까지의 최단 거리를 찾는 알고리즘) 등을 공부해왔었는데, 오늘은 플로이드-워셜 알고리즘을 공부해보았다.

오늘 풀어볼 BOJ 14938 문제이다.

알고리즘 분류를 보면 다익스트라와 플로이드-워셜 모두 사용 가능하다고 되어있지만, 

노드의 개수가 100으로 시간복잡도의 부담이 적고, 모든 노드를 시작점으로 잡고 최단거리를 구해야 하는 점,

음수 간선이 없는 점을 근거로 플로이드-워셜을 적용해 푸는 것이 쉽고 빠르다.

💡플로이드 워셜 알고리즘이란?

• 모든 정점에서 다른 모든 노드로 향하는 최단 경로를 구하는 알고리즘
• 모든 노드간의 최단 거리를 구하기에, 2차원 인접 행렬로 이루어짐.
• $O(N^3)$의 시간복잡도를 가진다. (각 경로에서 새로운 중간 노드로 사용할 수 있는 노드를 순차적으로 선택하고,더 짧은 길이를 선택하여 줄이는 과정을 반복하기 때문.)
• 음수 순환이 존재할 때는 사용불가.
  *(음수 순환 : 음수의 값을 가지는 간선이 있고, 주변에 연결된 간선들이 사이클을 이루는 경우)

👀다익스트라 알고리즘과의 차이점은?

• 다익스트라 알고리즘은, 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘.
• 따라서 출발 노드가 반드시 정해져있다.
• 가중치가 음수인 간선이 존재하면 사용할 수 없다.

⚒️플로이드 워셜 알고리즘의 원리

2차원 인접행렬로 직접 연결된 간선들을 표시한뒤, 여러 라운드를 거치며  중간노드로 사용할 수 있는 노드를 하나씩

선택하고, 짧은 길이를 선택하여 노드간의 길이를 줄이는 과정을 반복한다.

 

해당 문제를 예시로서,

최초의 노드간 거리 배열을 테이블로 그리면 다음과 같다.

NODE	1	2	3	4	5
1	0	3	INF	5	INF
2	3	0	3	INF	4
3	INF	3	0	INF	INF
4	5	INF	INF	0	INF
5	INF	4	INF	INF	0

1번 노드를 중간 노드로 지정하고, 새롭게 거리 배열을 업데이트 하면 다음과 같다.

NODE	1	2	3	4	5
1	0	3	INF	5	INF
2	3	0	3	8	4
3	INF	3	0	INF	INF
4	5	8	INF	0	INF
5	INF	4	INF	INF	0

2번 노드를 중간 노드로 지정하고, 새롭게 거리 배열을 업데이트 하면 다음과 같다.

4번에서 1번 노드를 거쳐 2번으로 가는 경로가 이전에 생겼으므로, 4➡️1➡️2➡️3 경로 또한 업데이트 가능하다.

또한, 2번에서 1번 노드를 거쳐 4번으로 가는 경로가 이전에 생겼으므로,2➡️4 경로가 존재하고,

5➡️2➡️4 (5➡️2➡️1➡️4) 경로 또한 가능하다.

NODE	1	2	3	4	5
1	0	3	6	5	7
2	3	0	3	8	4
3	6	3	0	11	7
4	5	8	11	0	12
5	7	4	7	12	0

3번 노드를 중간 노드로 지정하고, 새롭게 거리 배열을 업데이트 하면 다음과 같다. 변동사항이 없다.

NODE	1	2	3	4	5
1	0	3	6	5	7
2	3	0	3	8	4
3	6	3	0	11	7
4	5	8	11	0	12
5	7	4	7	12	0

.

.

.

이렇게 모든 노드를 한 번씩 중간노드로 지정하여 경로를 업데이트 하고나면, 각 노드에서 노드로 가는 최소 경로가 배열에 저장이 된다.

 

📜CODE

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

int n, m, r;
int item[101];
int dist[101][101];

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

  for (int i = 1; i <= n; i++) {
    for (int k = 1; k <= n; k++) {
      if (i == k) {
        dist[i][k] = 0;
      } else {
        dist[i][k] = INF;
      }
    }
  }

  int Pnode, Nnode, cost;
  while (r--) {
    cin >> Pnode >> Nnode >> cost;
    dist[Pnode][Nnode] = cost;
    dist[Nnode][Pnode] = cost;
  }

  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]);
      }
    }
  }

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