[BOJ] 백준 24042. 횡단보도

문제

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

24042번: 횡단보도

---

풀이

 다익스트라를 응용한 문제입니다. 

 

 일반적인 다익스트라 문제에서는 노드 간의 거리 비용을 가중치로 둡니다. 이 문제에서는 횡단 보도를 건너기 위해 기다려야하는 총 시간을 가중치로 두는 것이 핵심입니다.

 

 특히, 이 문제에서는 M이라는 주기 변수가 있습니다. 그래서 다음 노드로 진행하기전에 이 부분을 체크해주어야합니다.  주기 M을 고려하여 다음 노드로 이동하기 위해 기다려야 하는 시간을 계산해주어야 합니다. 

long temp = current.time % M; //1
temp = next.time - temp; //2
if (temp < 0) temp += M; //3
long nextTime = temp + current.time; //4

 

1. long temp = current.time % M; 

 현재 노드까지 도달하는 데 걸린 시간(current.time)을 주기 M으로 나눈 나머지를 계산합니다. 이 나머지는 현재 시간이 주기 내에서 몇 번째 순서인지를 나타냅니다. 예를 들어, M이 10이고 current.time이 23이라면, 현재 시간은 주기의 3번째 위치에 있음을 의미합니다 (23 % 10 = 3)

 

2. temp = next.time - temp; 

 다음 노드(next)로 이동하는 데 필요한 시간 순서(next.time)에서 위에서 계산한 temp 값을 빼줍니다. 현재 시간 위치로부터 다음 노드로 이동하기 위해 필요한 추가적인 시간을 구하는 것입니다.

 

3. if (temp < 0) temp += M;

 temp가 음수인 경우 (즉, 다음 노드로 이동하는 데 필요한 시간이 현재 주기의 위치보다 이전에 있을 경우)를 처리합니다. 음수 값이 나온다는 것은 이미 다음 이동 순서가 현재 주기에서 지나갔다는 것입니다. 따라서, 주기 M을 temp에 더함으로써 다음 주기로의 이동을 계산합니다. 

 

4. long nextTime = temp + current.time;

최종적으로 다음 노드에 도달하기까지의 총 시간입니다. 다음 노드로 이동할 때까지 기다려야 하는 총 시간을 의미합니다.

 

 

 

 추가로, M 범위가 700,000이고 N이 100,000이기 때문에 거리 배열을 Long값으로 잡아야합니다.

---

소스 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class B24042_횡단보도 {
    static int N,M;
    static long[] dist;
    static Long INF = Long.MAX_VALUE; // Long 주의!
    static class Node implements Comparable<Node>{
        int v;
        long time; //시간을 가중치로 잡는다.
        Node(int v, long time){
            this.v=v;
            this.time=time;
        }
        @Override
        public int compareTo(Node o){
            return (int)(time-o.time);
        }
    }
    static ArrayList<Node>[] list;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        dist = new long[N+1];
        Arrays.fill(dist,INF);
        list = new ArrayList[N+1];
        for(int i =0;i<N+1;i++){
            list[i] = new ArrayList<>();
        }
        for(int i=1;i<=M;i++){
            int st = sc.nextInt();
            int ed = sc.nextInt();
            list[st].add(new Node(ed,i));
            list[ed].add(new Node(st,i));
        }
        dijkstra(1);
        System.out.println(dist[N]);
    }
    static void dijkstra(int start){
        PriorityQueue<Node> queue = new PriorityQueue<>();
        dist[start] = 0;
        queue.add(new Node(start,0));

        while(!queue.isEmpty()){
            Node current = queue.poll();
            if(dist[current.v]<current.time) continue;

            for(Node next:list[current.v]){
                long order = current.time%M; //현재 시간이 주기내에서 몇번째 위치인지
                order = next.time-order; // 다음에 올 순서와 지금의 순서를 뺴준다.
                if(order<0) order+=M; //다음시간이 temp보다 작으면, 즉 순서가 낮으면 주기 더해주기 음수 값이 나온다는 것은 이미 다음 이동 순서가 현재 주기에서 지나갔다는 것
                long nextTime = order+current.time; // 최종적으로 다음 노드에 도달하기까지의 총 시간을 계산
                //이는 다음 노드로 이동할 때까지 기다려야 하는 총 시간

                if(dist[next.v]>nextTime){
                    dist[next.v] = nextTime;
                    queue.add(new Node(next.v,nextTime));
                }
            }
        }
    }
}