알고리즘/알문풀(백준, 프로그래머스, 코드트리)
[알고리즘] BOJ 11265 끝나지 않는 파티 (JAVA)
ragabys
2024. 5. 28. 12:58
https://www.acmicpc.net/problem/11265
백준 골드5로 난이도가 설정된 문제였다.
문제 지문에서 잡다한 내용을 다 빼고 보자면, 결국 A -> B 이동시 C 시간 이내로 올 수 있는지 없는지 출력해주면 된다는 것이었다.
도로는 일방통행이고, A와 B는 1 이상 N 이하의 모든 값이 될 수 있기 때문에
모든 정점에 대해 최단거리를 구하는 플로이드워셜 알고리즘을 사용했다.
보통의 플로이드워셜 문제가 INF 값을 임의로 설정하고 최단거리를 구하는 방식으로 구하는 반면에,
이 문제는 모든 정점 간의 거리가 입력으로 주어져서 딱히 그럴 필요가 없었다.
import java.io.*;
import java.util.*;
public class boj11265 {
static int N, M, A, B, C;
static int dist[][];
static StringBuilder sb;
public static void FLoydWrasahll() {
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
public static void pre() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
sb = new StringBuilder();
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
dist = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= N; j++) {
dist[i][j] = Integer.parseInt(st.nextToken());
}
}
FLoydWrasahll();
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
A = Integer.parseInt(st.nextToken());
B = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
sb.append(dist[A][B] <= C ? "Enjoy other party" : "Stay here").append('\n');
}
}
public static void main(String args[]) throws IOException {
pre();
System.out.print(sb);
}
}
해당 코드의 실행 시간은 다음과 같다.
