[플로이드 워셜] 개념과 예제 문제

플로이드 워셜 개념

i번 노드에서 j번 노드 사이 중간 노드의 거리를 반영하여 존재하는 모든 노드를 중간 노드로 두어보며 i->j 까지의 거리를 갱신한다. 결국 i->j 간 최단 거리(최소 비용의 거리)를 찾게 된다.

i와 j는 임의의 노드 번호가 될 수 있다. 결국 모든 노드 사이의 최단 거리(최소 비용의 거리)를 계산할 수 있다.

플로이드 워셜의 시간 복잡도는 O(V^3)이다.

source: https://www.youtube.com/watch?v=YiGxC9hAg4s

1. 초기 최단거리 테이블
   

2. 0번째 노드를 거쳐갈 때가 최소 비용의 거리인지 확인하고 그것이 맞다면 갱신 (k == 0)
   

3. 1번째 노드를 거쳐갈 때가 최소 비용의 거리인지 확인하고 그것이 맞다면 갱신 (k == 1)
   

4. 2번째 노드를 거쳐갈 때가 최소 비용의 거리인지 확인하고 그것이 맞다면 갱신 (k == 2)
   

5. 3번째 노드를 거쳐갈 때가 최소 비용의 거리인지 확인하고 그것이 맞다면 갱신 (k == 3)
   

---

템플릿 코드

#include <vector>
#include <iostream>
using namespace std;

const int LEN_MAX = 1e9;

void floydWarshall(int n, const vector<vector<pair<int, int>>>& graph, vector<vector<int>>& minDistTable) {
	// 최소 비용 테이블 초기화
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i == j)
				minDistTable[i][j] = 0;
			else
				minDistTable[i][j] = LEN_MAX;
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < graph[i].size(); j++) {
			int start = i;
			int end = graph[i][j].first;
			int cost = graph[i][j].second;

			minDistTable[start][end] = cost;
		}
	}

	// 플로이드 워셜 알고리즘 수행
	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (minDistTable[i][j] > minDistTable[i][k] + minDistTable[k][j])
					minDistTable[i][j] = minDistTable[i][k] + minDistTable[k][j];
			}
		}
	}	
}

int main() {
	int n;	// 노드의 수;
	cin >> n;
	// 노드 번호는 0 ~ n-1


	// 노드와 간선 정보를 담을 graph 자료구조
	vector<vector<pair<int, int>>> graph(n);

	int numOfEdge;
	cin >> numOfEdge;

	for (int i = 0; i < numOfEdge; i++) {
		int start, end, cost;
		cin >> start >> end >> cost;

		graph[start].push_back({ end, cost });
	}
	
	// 최단거리 테이블에 모든 노드에서 모든 노드로의 최단거리를 구한ㄷ.
	vector<vector<int>> minDistTable(n, vector<int>(n));

	floydWarshall(n, graph, minDistTable);

	cout << "print minDistTable" << endl;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << minDistTable[i][j] << ' ';
		}
		cout << endl;
	}
}

---

예제 문제: 역사_백준

source: https://www.acmicpc.net/problem/1613

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> distTable(400 + 1, vector<int>(400 + 1, 0));
// table[i][j] == 0: 전후 관계를 알 수 없음
// table[i][j] == -1: i번 사건이 j번 사건보다 먼저 일어남
// table[i][j] == 1: j번 사건이 i번 사건보다 먼저 일어남


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

	int n, m;
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;

		distTable[a][b] = -1;
		distTable[b][a] = 1;
	}

	// 플로이드 워셜을 이용한 연결관계 구하기
	// 모든 노드를 중가노드로 놓아가며 관계 구하기
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == j || i == k || j == k)
					continue;
				if (distTable[i][j] != 0)
					continue;

				if (distTable[i][k] == -1 && distTable[k][j] == -1) {
					distTable[i][j] = -1;
					distTable[j][i] = 1;	// 이 부분 주석처리 시 실패
				}
				else if (distTable[i][j] == 1 && distTable[k][j] == 1) {
					distTable[i][j] = 1;
					distTable[j][i] = -1;	// 이 부분 주석처리 시 실패
				}
			}
		}
	}

	int numOfQuery;
	cin >> numOfQuery;
	vector<int> queryAnswers;
	for (int i = 0; i < numOfQuery; i++) {
		int a, b;
		cin >> a >> b;
		queryAnswers.push_back(distTable[a][b]);
	}
	for (int i = 0; i < numOfQuery; i++) {
		cout << queryAnswers[i] << '\n';
	}
}

---

예제 문제: 회의준비_백준

source: https://www.acmicpc.net/problem/2610

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Union_Find {
public:
	int N;	// 사람 수
	// 그룹을 만들기 위한 테이블
	vector<int>* parentTable;

	// 유니온 파인드 초기화
	Union_Find(int n) {
		N = n;

		parentTable = new vector<int>(n + 1);
		for (int i = 1; i <= n; i++) {
			(*parentTable)[i] = i;
		}
	}

	int FindParent(int a) {
		if ((*parentTable)[a] == a)
			return a;

		return (*parentTable)[a] = FindParent((*parentTable)[a]);
	}

	void Union(int a, int b) {
		int aParent = FindParent(a);
		int bParent = FindParent(b);

		if (aParent < bParent)
			(*parentTable)[bParent] = aParent;
		else
			(*parentTable)[aParent] = bParent;
	}

	void makeGroup(vector<vector<int>>& groups) {
		vector<vector<int>> tempGroup(N + 1);
		for (int i = 1; i <= N; i++) {
			tempGroup[FindParent(i)].push_back(i);
		}

		for (int i = 1; i <= N; i++) {
			if (tempGroup[i].size() == 0)
				continue;

			groups.push_back(tempGroup[i]);
		}
	}

	~Union_Find() {
		delete parentTable;
	}
};



int main() {
	int n, m;
	cin >> n >> m;

	Union_Find uf(n);
	vector<vector<int>> minDistTable(n + 1, vector<int>(n+1, 1e9));
	for (int i = 1; i <= n; i++) {
		minDistTable[i][i] = 0;
	}
	
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		uf.Union(a, b);
		minDistTable[a][b] = 1;
		minDistTable[b][a] = 1;
	}
	
	// 그룹 만들기
	vector<vector<int>> groups;
	uf.makeGroup(groups);
	int numOfGroup = groups.size();

	// 각 그룹 플로이드 워셜처리
	for (int i = 0; i < numOfGroup; i++) {
		for (int k = 0; k < groups[i].size(); k++) {
			int pivot = groups[i][k];

			for (int s = 0; s < groups[i].size(); s++) {
				int start = groups[i][s];
				for (int e = 0; e < groups[i].size(); e++) {
					int end = groups[i][e];

					if (start == end)
						continue;

					if (minDistTable[start][end] > minDistTable[start][pivot] + minDistTable[pivot][end])
						minDistTable[start][end] = minDistTable[start][pivot] + minDistTable[pivot][end];
				}
			}
		}
	}

	// 각 그룹에서 대표 구하기

	vector<int> bosses;
	for (int i = 0; i < numOfGroup; i++) {
		int boss;
		int minLen = 1e9;
		for (int j = 0; j < groups[i].size(); j++) {
			int cand = groups[i][j];
			int len = 0;
			for (int k = 0; k < groups[i].size(); k++) {
				int link = groups[i][k];
				//len += minDistTable[cand][link];
				len = max(len, minDistTable[cand][link]);
			}
			if (minLen > len) {
				boss = cand;
				minLen = len;
			}
		}

		bosses.push_back(boss);
	}

	cout << numOfGroup << endl;
	sort(bosses.begin(), bosses.end());
	for (int i = 0; i < numOfGroup; i++) {
		cout << bosses[i] << endl;
	}
}