[C] 백준 - 11404번: 플로이드

9월 1일(금) - 그래프와 순회 (11404번)

11404번: 플로이드

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

 

- 플로이드 알고리즘은 이전에 풀이했던 "11403번: 경로 찾기" 문제에서 처음 활용해보았다

- 당시에는 플로이드 알고리즘인줄 모르고 풀이했지만, 이번 문제는 바로 활용해아하기에 아래 풀이를 참고

Floyd-Warshall(플로이드 와샬) 알고리즘

 

- 입력은 도시의 개수 n과 버스의 개수 m을 입력받고,

   m개의 줄에서 a(시작 도시), b(도착 도시), c(비용)를 입력받는다

- 풀이과정은

  1) 2중 for문으로 ( i != j )인 경우에만 INF로 초기화해주고,

  2) a,b,c가 입력되면 arr[ a ][ b ]와 c 중에서 더 작은 값을 arr[ i ][ j ]에 넣어주고,

  3) 플로이드 와샬 알고리즘 수행한다

- 출력은 n X n 개의 최소비용을 2중 for문을 사용해서

  arr[ i ][ j ]값이 INF와 다른 경우에만 arr[ i ][ j ]값을 출력하고,

  arr[ i ][ j ]값이 INF와 같다면 0을 출력한다

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>
#define INF 987654321

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

int MIN(int x, int y)
{
	return ((x < y) ? (x) : (y));
}

void floyd_warshell()
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			for (int k = 1; k <= n; k++)
			{
				if (arr[j][i] != INF && arr[i][k] != INF)
				{
					arr[j][k] = MIN(arr[j][k], arr[j][i] + arr[i][k]);
				}
			}
		}
	}
}

int main(void)
{
	scanf("%d", &n);
	scanf("%d", &m);

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (i != j)
			{
				arr[i][j] = INF;
			}
		}
	}

	int a, b, c;
	for (int i = 0; i < m; i++)
	{
		scanf("%d %d %d", &a, &b, &c);
		arr[a][b] = MIN(arr[a][b], c);
	}

	floyd_warshell();
	
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			int result = (arr[i][j] != INF) ? arr[i][j] : 0;
			printf("%d ", result);
		}
		printf("\n");
	}

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ