[파이썬] 백준 23286 : 허들 넘기 (골드3)

[파이썬] 백준 23286 : 허들 넘기 (골드3)

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

---

---

풀이

방향성 생각

• 현재까지 통과한 간선 중 최대값을 힙에 담아서 다익스트라.

 

---

전체코드

파이썬

import heapq as hq
import sys

input = lambda : sys.stdin.readline().rstrip()
INF = sys.maxsize

N,M,T = map(int,input().split())

G = [[] for _ in range(M+1)]
for _ in range(M):
    a,b,cost = map(int,input().split())
    G[a].append((b,cost))

def di(start):
    V = [INF]*(M+1)
    V[start] = 0

    heap = [(0,start)]    
    while heap:
        t,x = hq.heappop(heap)

        for nx,cost in G[x]:
            nt = max(t,cost)

            if nt < V[nx]:
                V[nx] = nt
                hq.heappush(heap,(nt,nx))
    return V

V = [None]
for i in range(1,N+1):
    V.append(di(i))

for _ in range(T):
    start,end = map(int,input().split())
    print(-1 if V[start][end] == INF else V[start][end])

• 힙에 들어가는 요소 업데이트만 잘 시켜주면 된다.

자바

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

public class Main {

    static final int INF = Integer.MAX_VALUE;
    static List<List<int[]>> G;
    static int[][] V;
    static int N, M, T;

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

        //  입력받기
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());

        // 초기화 + 간선 입력
        G = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            G.add(new ArrayList<>());
        }


        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            G.get(a).add(new int[] { b, cost });
        }


        // 다익 2차원배열 업데이트 V[start][end]
        V = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            V[i] = di(i);
        }


        // 출력버퍼
        StringBuilder sb = new StringBuilder();

        // 입력받아서 삼항 연산자로 값 설정하기
        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 = V[start][end];
            sb.append(result == INF ? -1 : result).append("\n");
        }
        System.out.print(sb.toString());
    }

    // 다익
    static int[] di(int start) {
        int[] distance = new int[N + 1];
        Arrays.fill(distance, INF);
        distance[start] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o[0]));
        pq.offer(new int[] { 0, start });

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int time = current[0];
            int node = current[1];

            if (time > distance[node]) continue;

            for (int[] edge : G.get(node)) {
                int nextNode = edge[0];
                int cost = edge[1];
                int newTime = Math.max(time, cost);

                if (newTime < distance[nextNode]) {
                    distance[nextNode] = newTime;
                    pq.offer(new int[] { newTime, nextNode });
                }
            }
        }
        return distance;
    }
}

• BufferedReader, StringTokenizer, PriorityQueue 등 익히기
• 자료구조 등 먼저 익히고 시작해야할듯...
• 메서드 등도 익히고, 변수명 최적화하기...

---

코멘트

• .