백준 11404번 : 플로이드

문제 접근

---

알고리즘 문제해결전략 책에서 플로이드-와샬 알고리즘 공부하고 풀었다. 이 알고리즘도 감은 오는데 직관적인 이해가 안 돼서 계속 풀어본 뒤 정리 한 번 해야 될 것 같다.

 

그래프를 하나씩 확장해나가며 갱신한다고 생각하면 될 것 같다. k 번 정점이 추가된 경로의 거리가 이 정점을 경유하지 않은 경로의 거리보다 짧다면 갱신하면서 결국에는 모든 정점쌍에 대한 최단 거리가 할당되는 것이다.

 

주의할 점!

1. 문제 조건 확실하게 확인할 것.

2. 범위 확실하게 지정할 것.

 

 

문제 코드

---

#include <iostream>
#include <algorithm>

using namespace std;

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

void floyd()
{
	for(int i=1; i<=n;++i)
		adj[i][i] = 0;
	
	for(int k=1; k<=n; ++k)
		for(int i=1; i<=n; ++i)
			for(int j=1; j<=n; ++j)
				if(adj[i][j] > adj[i][k] + adj[k][j])
				{
					adj[i][j] = adj[i][k] + adj[k][j];
					//cout<<"[UPDATE] "<<i<<"-"<<k<<"-"<<j<<" -> "<<adj[i][k]<<" + "<<adj[k][j]<<" = "<<adj[i][j]<<'\n';
				}
}

int main(void)
{
	const int INF = 1000000000;
	fill(&adj[0][0], &adj[100][100], INF);
	
	int a, b, c;
	cin>>n>>m;
	
	while(m--)
	{
		cin>>a>>b>>c;
		if(adj[a][b] > c)
			adj[a][b] = c;
	}
	
	floyd();	
	
	for(int i=1; i<=n; ++i)
	{
		for(int j=1; j<=n; ++j)
		{
			if(adj[i][j]!= INF)
				cout<<adj[i][j]<<' ';
			else
				cout<<"0 ";
		}
		
		cout<<'\n';
	}
}

 

테스트 케이스

---

다른 정점으로 이동이 불가할 때 0이 출력되는지 확인하기 위한 테스트케이스이다.

5
12
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
3 5 10
3 1 8
1 4 2
3 4 2

ans)

0 2 3 1 4
0 0 0 2 5
8 10 0 1 1
0 0 0 0 3
0 0 0 0 0