[백준] 23286번 - 허들 넘기(java)

Baekjoon 23286 - 허들 넘기 (클릭 시 이동)

문제

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

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	1024 MB	27	13	11	50.000%

입력

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

출력

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

풀이

플로이드 워셜을 써도 괜찮을 것 같지만 다익스트라 구현방법이 가물가물해서 다익스트라로 풀었다.

1. 모든 정점을 출발점으로 하여 다익스트라를 수행하는데 정점으로 이동할 때 허들 최소 높이를 저장한다.

   minHeight[i][temp.v] = Math.min(minHeight[i][temp.v], temp.h);

2. 이동 경로를 추적해야하기 때문에 route배열을 만들어 최소값이 갱신될 때 마다 이전 노드를 저장한다.

   route[i][temp.v] = curr.v;

3. 각각의 입력케이스에서 역추적을 통해 가장 높은 허들의 높이를 출력한다.

       static int findMin(int start, int end) {
           int res = 0;
           for (int i = 1; i <= N; i++) {
               while (end != 0) {
                   res = Math.max(res, minHeight[start][end]);
                   end = route[start][end];
               }
           }
           return res;
       }

최종 소스코드

package BJ_Practice;

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

public class BJ_G2_23286_허들_넘기 {

    static int N, M, T;
    static Node graph[];
    static int[][] minHeight;
    static int[][] route;
    static StringTokenizer st;

    static class Node implements Comparable<Node> {
        int v;
        int h;
        Node link;

        public Node(int v, int h, Node link) {
            super();
            this.v = v;
            this.h = h;
            this.link = link;
        }

        @Override
        public int compareTo(Node o) {
            return this.h - o.h;
        }
    }

    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());

        graph = new Node[N + 1];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());
            graph[u] = new Node(v, h, graph[u]);
        }
        // 입력 끝


        dijkstra();    // 다익스트라 수행 ( 플로이드 워셜로 대체 가능할 듯. )

        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            int result = findMin(start,end);    // 경로를 추적해서 최댓값을 가져옴.
            if(result == 100000000) result = -1;
            sb.append(result).append("\n");
        }
        System.out.println(sb.toString());
    }



    static void dijkstra() {
        minHeight = new int[N + 1][N + 1];
        route = new int[N + 1][N + 1];

        PriorityQueue<Node> pq = new PriorityQueue<>();
        for (int i = 1; i <= N; i++) {    // 모든 정점을 출발지로하여 다익스트라 수행.
            pq.clear();
            Arrays.fill(minHeight[i], 100000000);
            boolean[] visited = new boolean[N + 1];
            // 필요한 변수 초기화

            pq.offer(new Node(i, 0, graph[i]));
            minHeight[i][i] = 0;
            route[i][i] = 0;

            while (!pq.isEmpty()) {
                Node curr = pq.poll();

                if(visited[curr.v]) continue;
                visited[curr.v] = true;

                for (Node temp = graph[curr.v]; temp != null; temp = temp.link) {
                    if (!visited[temp.v] && minHeight[i][temp.v] > temp.h) {
                        pq.offer(new Node(temp.v, temp.h, null));
                        // 방문할 때 그 정점과 연결된 최소크기로 저장
                        minHeight[i][temp.v] 
                            = Math.min(minHeight[i][temp.v], temp.h);
                        route[i][temp.v] = curr.v;
                    }
                }
            }
        }
    }

    static int findMin(int start, int end) {
        int res = 0;
        for (int i = 1; i <= N; i++) {
            while (end != 0) {
                res = Math.max(res, minHeight[start][end]);
                end = route[start][end];
            }
        }
        return res;
    }
}