[boj][c++] 1389 케빈베이컨의6단계법칙, 11404 플로이드

1389 케빈 베이컨의 6단계 법칙

전형적인 플로이드워셜 알고리즘... dfs/bfs 분류에도 속해있다는데 그것도 대충 로직은 그려진다. 이전에 촌수계산 문제 풀었을 때와 비슷한 문제인 것 같다. 일단 오늘 학습한 내용으로 풀었는데 나중에 bfs 연습문제로 풀어보면 좋을 것 같다.

삼중반복문 돌려서 최단거리 테이블을 완성시킨 뒤에 각 노드마다 다른 노드로 가는 모든 거리를 더한 값을 min값과 비교했다. 그래서 바뀌면 그게 min임. 그때의 노드 번호를 출력하도록 작성했다.

#include	<iostream>
using namespace std;
#define INF 1e9

int graph[101][101];

int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < 101; i++)
	{
		for (int j = 0; j < 101; j++)
		{
			graph[i][j] = INF;
			if (i == j)
				graph[i][j] = 0;
		}
	}
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		graph[a][b] = 1;
		graph[b][a] = 1;
	}
	for (int i = 1; i <= n; i++)
	{
		for (int a = 1; a < 101; a++)
		{
			for (int b = 1; b < 101; b++)
			{
				graph[a][b] = min(graph[a][b], graph[a][i] + graph[i][b]);
			}
		}
	}
	int sum, ans;
	int min = INF;
	for (int i = 1; i <= n; i++)
	{
		sum = 0;
		for (int j = 1; j <= n; j++)
			sum += graph[i][j];
		if (sum < min)
		{
			min = sum;
			ans = i;
		}
	}
	cout << ans << endl;
}

---

11404 플로이드

새벽에 최단경로 문제를 너무 급하게 공부한 것 같아서 재정리할 겸 다시 풀어봤다. 새벽에 푼 문제보단 어려운 난이도였지만 근본적으로 최단경로를 구하는 방법은 같았고 작은 아이디어 하나만 있으면 돼서 무난하게 푼 문제다. 플로이드워셜 알고리즘을 알고있다면 이 문제는 입력받는 방법만 신경쓰면 된다.

• 같은 정점에 대해 가중치가 다른 간선이 여러개 있을 수 있다.
• 최단경로를 찾고 있기 때문에 같은 경로의 여러 가중치 중 가장 작은 가중치 값만 담아두면 된다
• 이후 과정은 위의 1389번 문제와 동일하다

#include	<iostream>
#define INF 1e9
using namespace std;

int graph[101][101];
int n, m;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			graph[i][j] = INF;
		}
	}
	for (int i = 0; i < m; i++)
	{
		int a, b, value;
		cin >> a >> b >> value;
		if (graph[a][b] > value)
			graph[a][b] = value;
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j < 101; j++)
		{
			for (int k = 1; k < 101; k++)
			{
				graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k]);
			}
		}
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (graph[i][j] == INF || i == j)
				cout << "0" << ' ';
			else
				cout << graph[i][j] << ' ';
		}
		cout << '\n';
	}
}