[백준_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)는 지금으로부터 다음 파티가 열리는데 걸리는 시간을 의미한다.

 

[코드]

import java.util.*;

public class BaekJoon_11265 {
	static int[][] graph;
	static int n,m;
	static final int INF=(int)1e9;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		
		graph=new int[n+1][n+1];
		
		/*
		 * 자신이 자신에게로 가는 경로는 0으로 초기화
		 * 외의 지점은 최댓값으로 초기화 
		 */
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				if(i==j)
					graph[i][j]=0;
				else 
					graph[i][j]=INF;
			}	
		}
		
		// 값 입력 받기
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				graph[i][j]=sc.nextInt();
		
		// 플로이드 워셜 알고리즘을 사용하여 최단경로로 갱신
		for(int k=1;k<=n;k++) 
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					graph[i][j]=Math.min(graph[i][j], graph[i][k]+graph[k][j]);
		
		for(int i=0;i<m;i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			int c=sc.nextInt();
			
			// 시간 내에 도착할 수 있는 경우
			if(graph[a][b]<=c)
				System.out.println("Enjoy other party");
			// 시간 내에 도착할 수 없는 경우
			else 
				System.out.println("Stay here");
		}
	}
}

 

[고찰]

 이번 문제는 플로이드 워셜 알고리즘을 사용하여 각 노드마다 다른 모든 노드로 가는 최단 경로를 찾는 문제이다. 이런 방법으로 문제를 풀었음에도 처음에는 오답 처리를 받았다. 고민 끝에 찾아낸 이유는 배열의 초기화를 해주지 않았던 것이다. 자기 자신으로 가는 경우를 제외하고는 모두 최댓값으로 초기화를 해주는 과정이 필요했다.