[BOJ] 백준 23286 : 허들 넘기 (java)

🧪 23286 허들 넘기

---

난이도 : 🌟 골드 3
유형 : 플로이드-워셜

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

 

📝 문제

---

허들 국가대표를 꿈꾸는 연두는 그래프 위에서 허들 넘기를 연습하려고 한다. 연두가 연습할 그래프는 정점이 N개 있고, 간선이 M개 있다. 간선은 방향성이 있어, 1에서 2로 가는 길이 있더라도, 2에서 1로 가는 길은 없을 수도 있다. 간선 위에는 허들이 중간에 놓여 있고, 간선을 지나갈 때는 반드시 허들을 넘어야 한다.

연두는 연습을 T번 할 것이고, 각 연습마다 출발 정점과 도착 정점을 미리 정해놓았다. 연두가 힘들지 않게 연습을 하기 위해, 각 연습마다 출발 정점에서 도착 정점으로 가는 경로 중에서 가장 높이가 높은 허들의 높이가 최소가 되는 것을 찾아보자.

 

입력

 

첫째 줄에 세 정수 N, M, T가 주어진다. 다음 M개의 줄에 그래프 간선의 정보 u, v, h가 주어지고, u에서 v로 가는 간선이 있고, 높이가 h인 허들이 간선 중간에 놓여 있다는 의미이다. 마지막 T개의 줄에는 연습의 정보 s, e가 한 줄에 하나씩 주어진다. s는 출발 정점, e는 도착 정점을 의미한다.

 

출력

 

 

입력으로 주어진 연습 마다 한 줄에 하나씩 출발 정점에서 도착 정점으로 가는 경로 중 가장 높은 허들 높이의 최솟값을 출력한다. 만약 출발 정점에서 도착 정점으로 갈 수 없는 경우 -1을 출력한다.

 

🚧  주의할 점

---

 

🧐 핵심 로직 

---

1. fillGraph 메서드는 입력으로 주어진 간선 정보를 바탕으로 그래프를 초기화한다.

    1 - 1)  먼저 n + 1 × n + 1 크기의 2차원 배열을 생성하고, 자기 자신을 제외한 모든 정점 간 거리를 INF로 설정한다.

    1 - 2)  이후 m개의 간선 정보를 읽어와, 시작 정점 u에서 도착 정점 v로 가는 가중치 h를 graphs[u][v]에 저장한다.

    1 - 3)  이는 단방향 그래프이며, 간선이 여러 개 들어올 수 있으므로 가장 마지막에 입력된 가중치로 덮어쓴다.

 

2. floydWarshall 메서드는 플로이드-워셜 알고리즘을 사용하여 최대 최소 비용 경로를 구한다.

    2 - 1)  일반적인 플로이드-워셜 알고리즘에서는 min()을 통해 모든 정점 간 최소 거리 합을 구하지만, 이 문제에서는 두 경로 중 더 긴 경로를 최소화해야 하므로 max()를 사용하여 중간 경유지를 지날 경우의 최대값 중 가장 작은 값을 구한다.

    2 - 2)  조건문은 현재 i → j로 바로 가는 비용이 i → k와 k → j로 거쳐 가는 비용보다 큰 경우에만 업데이트를 수행한다.

 

3. printResult 메서드는 주어진 t개의 질의에 대해 두 지점 s에서 e로 가는 최소 최대비용을 출력한다.

    3 - 1)  graphs[s][e]의 값이 INF이면 경로가 없다는 의미이므로 1을 출력하고,

    3 - 2)  그 외에는 해당 값을 그대로 출력한다.

 

4. 최종적으로 프로그램은 입력 파일에서 정점 수, 간선 수, 질의 수를 읽은 후 그래프를 초기화하고, 플로이드-워셜 알고리즘을 적용한 뒤, 각 질의에 대한 결과를 출력한다.

 

💻 최종 코드 (636 ms)

---

import java.util.*;
import java.io.*;

public class Main {

    static final int INF = 123456789;

    static BufferedReader br;
    static int n, m, t;
    static int[][] graphs;
    public static void main(String[] args) throws Exception {

//      br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new FileReader("input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        t = Integer.parseInt(st.nextToken());

        fillGraph();
        floydWarshall();
        printResult();

        br.close();
    }

    private static void fillGraph() throws Exception {

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

        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());

            graphs[u][v] = h;
        }
    }

    private static void floydWarshall() {

        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (graphs[i][j] > graphs[i][k] && graphs[i][j] > graphs[k][j]) {
                        graphs[i][j] = Math.max(graphs[i][k], graphs[k][j]);
                    }
                }
            }
        }
    }

    private static void printResult() throws Exception {

        for (int i = 0; i < t; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            System.out.println(graphs[s][e] == INF ? -1 : graphs[s][e]);
        }
    }
}