백준 24042번: 횡단보도 (Java)

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

24042번: 횡단보도

 

 

 

---

 

문제 알고리즘을 파악하는 것이 쉽지 않은 문제인 듯하다. 다만 나는 다익스트라 문제집을 풀고 있었어서 기본적으로 뭔지는 알고 풀었다.

 

풀이

다익스트라인걸 알았으면, 각 횡단보도를 건넌 후, 도착한 시간에 따라 다음 횡단보도를 건널 수 있는 최소 시간을 적절히 구하면 된다.

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
    
    static final long INF = Long.MAX_VALUE;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<Edge>());
        }
        
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            graph.get(u).add(new Edge(v, i));
            graph.get(v).add(new Edge(u, i));
        }
        
        long[] d = new long[N+1];
        Arrays.fill(d, INF);
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(1, 0));
        d[1] = 0;
        while (!pq.isEmpty()) {
            Edge cur = pq.poll();
            int curLoc = cur.loc;
            long curDist = cur.dist;
            if (d[curLoc] < curDist) continue;
            for (Edge nxt: graph.get(curLoc)) {
                int nxtLoc = nxt.loc;
                long nxtDist;
                if (curDist <= nxt.dist) nxtDist = nxt.dist + 1;
                else {
                    nxtDist = ((long) Math.ceil(((double)curDist-nxt.dist)/M)) * M + nxt.dist + 1;
                }
                if (nxtDist < d[nxtLoc]) {
                    d[nxtLoc] = nxtDist;
                    pq.offer(new Edge(nxtLoc, nxtDist));
                }
            }
        }
        System.out.println(d[N]);
    }
    
    static class Edge implements Comparable<Edge> {
        int loc;
        long dist;
 
        public Edge(int loc, long dist) {
            this.loc = loc;
            this.dist = dist;
        }
 
        public int compareTo(Edge o) {
            return Long.compare(this.dist, o.dist);
        }
    }
}