(백준 11403번 경로찾기 / 백준 1389번 케빈 베이컨의 6단계 법칙) (라이님 블로그 대회 알고리즘 따라잡기 18) 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)

직관적인 플로이드 와샬 알고리즘 같은 알고리즘만 있으면 얼마나 좋을까..ㅎㅎ

 

플로이드 와샬 알고리즘만 있으면 쉽게 풀리는 두 개의 문제를 풀어보았다.

 

백준 11403번

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

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

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

	int N; cin >> N;
	bool dist[100][100];

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> dist[i][j];
		}
	}

	for (int k = 0; k < N; k++) {
		for (int i = 0; i < N; i++) {
			if (dist[i][k] == 0) continue;
			for (int j = 0; j < N; j++) {
				if (dist[k][j] != 0) dist[i][j] = 1;
			}
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << dist[i][j] << " ";
		}
		cout << "\n";
	}

	return 0;
}

 

백준 1389번

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

★ min_sum의 최대값을 너무 작은 값을 넣어 안 돌아갔는데, 수정하니까 작동된다!

참고로 min_sum의 최대값은 100 * 100이 되는데, 각 사람은 최대 100단계 이내로 아는 사람을 연결할 수 있고, 케빈 베이컨 게임을 하는 사람이 최대 100명이기 때문이다.

 

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

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

	int dist[100][100] = { 0 };
	int N, M; cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int u, v; cin >> u >> v;
		dist[u - 1][v - 1] = 1;
		dist[v - 1][u - 1] = 1;
	}

	for (int k = 0; k < N; k++) {
		for (int i = 0; i < N; i++) {
			if (dist[i][k] == 0) continue;
			for (int j = 0; j < N; j++) {
				if (i == j) continue;
				if (dist[k][j] != 0) {
					if (dist[i][j] == 0) dist[i][j] = dist[i][k] + dist[k][j];
					else dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
				}
			}
		}
	}

	int min_sum = 20000;
	int index;
	for (int i = 0; i < N; i++) {
		int sum = 0;
		for (int j = 0; j < N; j++) {
			if (i == j) continue;
			sum += dist[i][j];
		}
		if (min_sum > sum) {
			min_sum = sum;
			index = i;
		}
	}
	cout << index + 1;
	return 0;
}