[백준] 11265 - 끝나지 않는 파티

1. 문제

11265번: 끝나지 않는 파티

2. 개요

한 놀이동산이 있고 놀이동산에 여러 파티장들이 있다.

파티장들은 서로 일방통행인 도로로 연결되어 있다.

출발 파티장과 도착 파티장, 제한시간이 입력으로 주어졌을 때 제한시간 내에 이동이 가능하다면 “Enjoy other party”, 그렇지 않다면 “Stay here”을 출력하는 문제.

2-1. 플로이드 워셜

모든 정점에서의 모든 정점까지의 최단거리를 구해야 하므로 플로이드 워셜 알고리즘을 활용한다.

(한 정점에서 다른 모든 정점까지라면 다익스트라 알고리즘.)

플로이드 워셜 알고리즘의 개념은 이렇다.

시작 노드 s에서 도착 노드 e까지의 최단 거리를 구하기 위해 시작 노드 s → 중간 노드 m의 최단거리와 중간 노드 m → 도착 노드 e의 최단거리를 이용한다.

출발노드를 행, 도착노드를 열로 하는 아래와 같은 그래프의 경우를 생각해보자.

	1	2	3	4
1	0	4	7	2
2	2	0	6	3
3	1	9	0	4
4	8	1	10	0

1 → 2의 최단거리를 구해보자.

각 식은 시작 → 도착 ? 시작 → 중간 + 중간 → 도착이다.

1 → 2 ? 1 → 1 + 1 → 2   	  4 = 0 + 4

1 → 2 ? 1 → 2 + 2 → 2   	  4 = 4 + 0

1 → 2 ? 1 → 3 + 3 → 2   	  4 < 7 + 9

1 → 2 ? 1 → 4 + 4 → 2   	  4 > 1 + 2

따라서 1 → 2의 최단거리는 1 → 4 → 2, 2 + 1 = 3이 나오게 된다.

이 같은 방식을 모든 노드를 대상으로 진행해나가면 된다.

기본적인 플로이드 워셜 알고리즘을 코드로 나타내면 다음과 같다.

for (int m = 0; m < N; m++)          // 중간 노드
{
	for (int s = 0; s < N; s++)        // 시작 노드
	{
		for (int e = 0; e < N; e++)      // 도착 노드
		{
			if (graph[s, e] > graph[s, m] + graph[m, e])  // 중간 노드 경유가 더 효율적이라면
				graph[s, e] = graph[s, m] + graph[m, e]     // 교체.
		}
	}
}

3. 코드 및 추가내용

3-1. Python

import sys

N, M = map(int, sys.stdin.readline().split())

graph = []
for i in range(N):
    graph.append(list(map(int, sys.stdin.readline().split())))

for m in range(N):
    for s in range(N):
        for e in range(N):
            if graph[s][e] > graph[s][m] + graph[m][e]:
                graph[s][e] = graph[s][m] + graph[m][e]

for i in range(M):
    s, e, dist = map(int, sys.stdin.readline().split())

    if graph[s-1][e-1] <= dist:
        print("Enjoy other party")

    else:
        print("Stay here")

3-2. C#

class Program
{
	static void Main(string[] args)
	{
		int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
		int N = input[0];
		int M = input[1];

		int[,] graph = new int[N, N];

		for (int i = 0; i < N; i++)
		{
			input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

			for (int j = 0; j < N; j++)
			{
				graph[i, j] = input[j];
			}
		}

		for (int m = 0; m < N; m++)
		{
			for (int s = 0; s < N; s++)
			{
				for (int e = 0; e < N; e++)
				{
					if (graph[s, e] > graph[s, m] + graph[m, e])
						graph[s, e] = graph[s, m] + graph[m, e];
				}
			}
		}

		for (int i = 0; i < M; i++)
		{
			input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
			int start = input[0] - 1;
			int end = input[1] - 1;
			int dist = input[2];

			if (graph[start, end] <= dist)
				Console.WriteLine("Enjoy other party");

			else
				Console.WriteLine("Stay here");
		}
		
	}
}