백준 | 11265번. 끝나지 않은 파티 - 플로이드

⬛ 백준 11265번. 끝나지 않은 파티 - 플로이드

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

11265번: 끝나지 않는 파티

문제

파티를 좋아하는 민호는 끝없이 파티가 열리는 놀이동산 "민호월드"를 세웠다. 처음에는 한개의 파티장만을 가지고 있는 작은 놀이동산이었지만, 사람들의 점점 많이 찾아와 파티장을 증축했고 현재는 N개의 파티장을 가진 큰 놀이동산이 되었다. 민호는 파티장을 증축할때마다 편의를 위해 새로운 파티장과 기존의 모든 파티장이 직접적으로 연결이 될 수 있는 도로들을 만들었다. 이때 만들어진 도로들은 사용자들의 편의를 위해 일방통행으로 설계가 되었다.

파티장이 적을때는 괜찮았지만 파티장이 많아진 지금 다음과 같은 두 가지 문제점이 발생했다.

1. A 파티장에서 B 파티장으로 빨리 갈 수 있도록 직접 연결이 된 일방통행 도로를 만들었지만 A와 B가 아닌 다른 파티장을 경유해서 더 빨리 갈 수 있는 경우가 있을 수 있다.
2. 지금으로부터 C만큼의 시간 뒤에 B번 파티장에서 새롭게 파티가 열리는데 1번과 같은 이유때문에 현재 있는 A파티장에서 B번 파티장까지 파티가 열리는 시간까지 맞춰 갈 수 있는지 쉽게 알 수 없다.

이러한 문제점으로 이용객들의 불만이 점점 커져갔고 민호는 이를 해결하기 위해 빠른 네비게이션 서비스를 실행하기로 하였으나 서비스 요청이 너무 많아 업무가 마비되기에 이르렀다. 이에 민호는 천재프로그래머인 당신에게 이 문제를 해결해 달라고 요청하였다. 민호를 도와 한 파티장에서 다른 파티장에까지 시간내에 도착할 수 있는지 없는지 알아봐주는 프로그램을 작성하자.

입력

입력의 첫 번째 줄에는 파티장의 크기 N(5 ≤ N ≤ 500)과 서비스를 요청한 손님의 수 M(1 ≤ M ≤ 10,000) 이 주어진다. 각각의 파티장은 1번부터 N번까지 번호가 붙여져 있다. 다음에는 N개의 줄에 걸쳐 각각 N개의 수가 주어진다. i번째 줄의 j번째 수 T(1 ≤ T ≤ 1,000,000)는 i번 파티장에서 j번 파티장으로 직접적으로 연결된 도로를 통해 이동하는 시간을 의미한다.

다음 M개의 줄에는 세개의 정수 A, B, C가 주어진다. A(1 ≤ A ≤ N) 는 서비스를 요청한 손님이 위치한 파티장의 번호, B(1 ≤ B ≤ N) 다음 파티가 열리는 파티장의 번호, C(1 ≤ C ≤ 1,000,000,000)는 지금으로부터 다음 파티가 열리는데 걸리는 시간을 의미한다.

출력

M개의 줄에 걸쳐 서비스를 요청한 손님이 시간내에 다른 파티장에 도착할 수 있으면 “Enjoy other party”를, 시간내에 도착할 수 없으면 "Stay here”를 출력한다.

---

💚나의 풀이

• 입력으로 들어오는 i → j로의 직접 연결된 도로 이동 시간을 인접 행렬로 입력받아두고,
• 플로이드로 경유지 k를 거쳐 기존 거리보다 짧게 갈 수 있는 최단 거리를 발견하면 갱신되도록 처리한다.
• 이후 손님이 요청한 M개의 서비스 요청을 최단거리로 세팅해둔 distance에서 확인하여 다음 파티장으로 가는 C 시간 이내 갈 수 있으면 Enjoy를 출력하고, 못 가면 Stay를 출력하도록 로직을 짰다.

package to_0906_7;

import java.util.*;

/*11265번. 끝나지 않는 파티 - 플로이드 */
public class Main {
	static int N, M;
	static int[][] distance;
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		N = kb.nextInt();
		M = kb.nextInt();
		
		distance = new int[N+1][N+1];//기본 거리 
		
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				distance[i][j] = kb.nextInt();
			}
		}
		
		//우선 업데이트 시키자. 
		//플로이드 
		for(int k=1; k<=N; k++) {
			for(int i=1; i<=N; i++) {
				for(int j=1; j<=N; j++) {
					//기존 경로보다 k를 거쳐서 더 최단 거리로 갈 방법 존재하면 갱신시킨다.
					if(distance[i][j] > distance[i][k] + distance[k][j]) {
						distance[i][j] = distance[i][k] + distance[k][j];
					}
				}
			}
		}
		
		//이제 완전 최단 경로로 세팅한 상태에서 요청 M개의 서비스를 확인
		ArrayList<String > answer = new ArrayList<>();
		
		for(int i=0; i<M; i++) {
			int a= kb.nextInt();
			int b = kb.nextInt();
			int T = kb.nextInt();//이 기준 시간 내에 갈 수 있냐 ? 
			
			if(distance[a][b] <= T) answer.add("Enjoy other party");
			else if(distance[a][b] > T) answer.add("Stay here");
		}
		
		//완성된 상태 출력 
		for(String x : answer) {
			System.out.println(x);
		}
	}
}