백준 24042 (횡단보도) - java

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

24042번: 횡단보도

문제

유형 : 다익스트라

접근 방식

• 기존의 다익스트라 유형과는 다르게 주기라는 개념에 대한 이해가 필요하다.
  • 다음 주기 이전에 도착했다면? -> 이동하지 못하고 주기를 기다려야 한다.
  • 주기 이후에 도착했다면? -> 다음 주기까지 기다려야 한다.
• 즉 주기마다 이동할 수 있기 때문에 dis[] 배열에 주기를 저장해야 한다.
• 주기 계산 방법 !
  • 임이의 지점에 T 초에 도착했다고 하자 ! 다음 지점의 주기를 구하는 방법은 다음과 같다.
    • a (다음 신호 차수) , M( 주기 시간) , i (다음 지점의 지역 번호 : 위 문제에서는 지역 번호에 따라 주기가 다르다)

주기 계산 코드

            for(Node next : graph[cur.v]){
                long curT = (cur.t - next.idx);

                if(curT < 0)
                    curT = 0;

                else {
                    curT = curT / m;
                    curT = curT + 1;
                }

                if(dis[next.v] > next.idx + (curT * m)){
                    dis[next.v] = next.idx + (curT * m);

                    pq.add(new Node(next.v,dis[next.v],next.idx));
                }

            }

전체 코드

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

public class Main {
    static int n = 0;
    static int m = 0;
    static ArrayList<Node>[] graph;
    static final long NOT = 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(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        graph = new ArrayList[n+1];
        for(int i=1;i<=n;i++){
            graph[i] = new ArrayList<>();
        }

        for(int i=1;i<=m;i++){
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            graph[x].add(new Node(y,i,i));
            graph[y].add(new Node(x,i,i));
        }


        search();

        br.close();
    }

    static void search(){
        boolean[] v = new boolean[n+1];
        v[1] = true;

        PriorityQueue<Node> pq = new PriorityQueue<>(
                (x,y) -> Long.compare(x.t,y.t)
        );

        long[] dis = new long[n+1];
        for(int i=2;i<=n;i++){
            dis[i] = NOT;
        }

        for(Node tmp : graph[1]){
            dis[tmp.v] = tmp.idx;
            pq.add(new Node(tmp.v,dis[tmp.v],tmp.idx));
        }


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

            if(cur.v == n){
                System.out.println(cur.t);
                break;
            }

            if(v[cur.v])
                continue;

            v[cur.v] = true;

            for(Node next : graph[cur.v]){
                long curT = (cur.t - next.idx);

                if(curT < 0)
                    curT = 0;

                else {
                    curT = curT / m;
                    curT = curT + 1;
                }

                if(dis[next.v] > next.idx + (curT * m)){
                    dis[next.v] = next.idx + (curT * m);

                    pq.add(new Node(next.v,dis[next.v],next.idx));
                }

            }
        }

    }

    static void print(long[] dis){
        for(int i=1;i<=n;i++){
            System.out.print(dis[i]+" ");
        }
        System.out.println();
    }
}
class Node{
    int v;
    long  t;

    long idx;

    Node(int v,long t,long idx){
        this.v = v;
        this.t = t;
        this.idx = idx;
    }
}