백준 11404번_플로이드

2020-04-03 · 배운 것 · 4분 읽기

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

11404번: 플로이드

1. 풀이 방법

이 문제 이름처럼 모든경로의 최단경로를 알수있는 기본적인 플로이드 와샬 알고리즘을 이용하면 손쉽게 풀수있다.
플로이드 와샬 알고리즘은 모든 정점을 돌며 각 정점을 중간지점으로 갖는 곳을 기준으로 최단거리를 갱신하며 풀어간다.

위의 그림에서 1 에서 3번으로 가고 싶을때는 1-> 3으로 가는 직통, 1-> 2 -> 3으로 2를 경유해서 가는 경로 2 가지가 있다. 이때 그림 옆처럼 2차원 배열을 만들어 직통으로 연결된 곳들을 초기화 해준다. ( 직통이 없는 경우는 무한대로 해야함 )

이후, 모든 정점 1 ~ n 을 돌며 그 정점을 중간지점으로 갖는 곳을 비교해준다.

ex) 위에 그림에서 1- > 3 ( 3 ) 보다 1-> 2 ( 1 ) + 2 -> 3 ( 1 ) = 2 가 더 작으므로

위처럼 바꿔주면 되겠다.

2. 코드

#include<iostream>
#include <algorithm>
#include <vector>
#include <limits.h>

#define LIMIT 987654321

using namespace std;

int floyed[102][102];

void floyedInit(int n)
{
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
		{
			if (i == j)
			{
				floyed[i][j] = 0;
				continue;
			}
			floyed[i][j] = LIMIT;
		}
}

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

	//1. 배열 초기화, 직접적으로 연결되지 않은곳은 무한대로 둔다
	floyedInit(n);
	int a, b, c;
	for (int i = 0; i < m; i++)
	{
		cin >> a >> b >> c;
		floyed[a][b] = min(floyed[a][b], c);
	}

	//2. 모든 정점을 돌며 그  정점을 중간지점으로 갖는 곳을 바꿔준다
	//정점은 1부터 ~
	for (int mid = 1; mid <= n; mid++)
	{
		for (int start = 1; start <= n; start++)
		{
			//중간지점이 자기자신이 될순 없다.
			if (start == mid)
				continue;
			for (int end = 1; end <= n; end++)
			{
				//끝지점이 중간지점이 될순 없다, 시작점과 끝점이 같은 경우는 계산할필요가 없음
				if (end == mid || start == end)
					continue;

				int comp = floyed[start][mid] + floyed[mid][end];
				floyed[start][end] = min(floyed[start][end], comp);
			}
		 }
	}

	//만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (floyed[i][j] == LIMIT)
				floyed[i][j] = 0;
	
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
			cout << floyed[i][j] << ' ';
		cout << endl;
	}

	return 0;
}

3. 후기

내 글을 누가 많이 읽는건 아니지만 요즘 글쓰는 맛에 공부한다. ㅋㅋㅋㅋ