24042. 횡단보도

오리구이·2026년 4월 24일

백준 알고리즘

코딩테스트

목록 보기

2/14

문제

[BOJ-24042] 횡단보도

문제 해결 아이디어

시간 그래프에서 다음 파란불까지 대기 시간을 간선 가중치로 바꾼 다익스트라

조건

주기 M분, 매 분마다 딱 하나의 횡단보도만 파란불
신호 i (0-indexed): t ≡ i (mod M) 일 때 파란불 → 그 순간에 건너기 시작해야 함
현재 시각 t에서 period p 횡단보도를 이용하려면 t' ≡ p (mod M)인 가장 가까운 미래 t'까지 대기
N, M이 크므로 최대 시간 ≈ N × M → long 필수

다익스트라 접근

times[v] : 1번 지역에서 v까지 도달하는 최소 시간 (long 배열)
간선 가중치 = 다음 파란불까지 대기 시간 + 1 (건너는 시간)
현재 시각 t에서 period p 횡단보도를 이용할 때 도착 시각:

대기 시간 계산

curP = t % M (현재 주기 내 위치)

조건	대기	도착 시각
curP == p	0	t + 1
curP < p	p - curP	t + (p - curP) + 1
curP > p	M - curP + p	t + (M - curP + p) + 1

코드

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

public class BOJ_24042 {
    static int N;
    static int M;
    static List<List<Crosswalk>> graph = new ArrayList<>();
    static long[] times;

    static class Crosswalk {
        int nx;
        int p;

        Crosswalk (int nx, int p) {
            this.nx = nx;
            this.p = p;
        }
    }

    static class Node {
        int x;
        long t;

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

    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());

        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int x = Integer.parseInt(st.nextToken());
            int nx = Integer.parseInt(st.nextToken());

            graph.get(x).add(new Crosswalk(nx, i));
            graph.get(nx).add(new Crosswalk(x, i));
        }

        times = new long[N+1];
        Arrays.fill(times, Long.MAX_VALUE);
        times[1] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingLong((Node n) -> n.t)
                                                         .thenComparingInt((Node n) -> n.x));
        pq.add(new Node(1, 0));

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

            if (cur.t > times[cur.x]) continue;

            for (Crosswalk nc : graph.get(cur.x)) {
                int curP = (int)(cur.t % M);
                long nt = cur.t + 1;

                if (curP < nc.p) {
                    nt += nc.p - curP;
                } else if (curP > nc.p) {
                    nt += (M - curP) + nc.p;
                }

                if (nt < times[nc.nx]) {
                    times[nc.nx] = nt;
                    pq.add(new Node(nc.nx, nt));
                }
            }
        }

        System.out.println(times[N]);
    }
}