24042번 - 횡단보도

2025-05-28

#JAVA#백준

3분

문제 링크

문제 풀이 시간 : 1시간

문제 요약

•
N개의 지역(1번부터 N번까지)이 있고, 이들을 잇는 M개의 횡단보도가 있음

•
각 횡단보도는 1분간 파란불이 들어오고, M분 주기로 반복됨

•
i번째 입력은 i, i+M, i+2M, ... 분에 해당 횡단보도에 파란불이 들어옴

•
사람이 횡단보도를 건널 수 있는 시간은 오직 파란불이 들어온 순간부터 1분 간뿐임

•
시작 지점은 1번 지역, 도착 지점은 N번 지역

•
0분부터 출발하여 최소 시간으로 도착해야 함

문제 풀이

이 문제는 보자마자 다익스트라가 떠오르는 문제였다.

하지만 일반적인 다익스트라와는 다르게 간선을 특정 시간에만 사용할 수 있기 때문에 간선을 사용할 수 있는 조건을 만족하도록 대기 시간을 적절하게 계산해야 한다.

횡단보도 연결 정보

Java

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 Node(v, i));
    graph.get(v).add(new Node(u, i));
}

i번째 입력의 횡단보도에 대해 파란불이 들어오는 시간은 i+k*M 이다. (k는 임의의 정수)

따라서 i를 해당 횡단보도의 파란불 시작 시간으로 저장해두었다.

최소 시간 계산(다익스트라 + 대기 시간)

Java

public static void find() {
    PriorityQueue<State> pq = new PriorityQueue<>(Comparator.comparingLong(s -> s.time));
    pq.offer(new State(1, 0)); // 시작 지역 1번, 시간 0
    dist[1] = 0;

    while (!pq.isEmpty()) {
        State now = pq.poll();

        if (now.time > dist[now.index]) continue;

        for (Node next : graph.get(now.index)) {
            long nextTime;

            // 현재 시간이 신호 시간보다 이르면 기다릴 필요 없음
            if (now.time <= next.signalTime) {
                nextTime = next.signalTime + 1; //이동하는 시간 1분을 더함
            } else {
                // 기다려야 하는 경우: 다음 파란불 시간을 계산
                long wait = ((now.time - next.signalTime + M - 1) / M) * M;
                nextTime = wait + next.signalTime + 1; //이동 시간 1분 더함
            }

            // 더 짧은 경로를 발견하면 갱신
            if (nextTime < dist[next.to]) {
                dist[next.to] = nextTime;
                pq.offer(new State(next.to, nextTime));
            }
        }
    }
}

신호가 들어오는 다음 시간을 (현재 시간 - 신호 시작 시간) / M 을 통해 계산한다.

전체 코드

Java

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

class Main {
    public static int n, m;
    public static List<List<Node>> graph;
    public static long[] dist;

    static class Node {
        int to; //도착 노드 번호
        int signalTime; // 횡단 보도에 처음 파란불이 들어오는 시간

        public Node(int to, int signalTime) {
            this.to = to;
            this.signalTime = signalTime;
        }

    }
    static class State { 
        int index; //현재 번호
        long time; //현재까지 걸린 시간

        public State(int index, long time) {
            this.index = index;
            this.time = time;
        }

    }

    public static void find() {
        PriorityQueue<State> pq = new PriorityQueue<>(Comparator.comparingLong(s -> s.time));
        pq.offer(new State(1, 0));
        dist[1] = 0;

        while (!pq.isEmpty()) {
            State now = pq.poll();
	          // 이미 더 짧은 경로로 방문되었다면 패스
            if (now.time > dist[now.index]) continue;
            // 현재 노드에서 이동 가능한 모든 이웃 체크
            for (Node next : graph.get(now.index)) {
                long nextTime;
                // 현재 시간이 signalTime 이전이라면 다음 파란불 시각 이전이라 해당 시간까지 기다렸다 출발
                if (now.time <= next.signalTime) {
                    nextTime = next.signalTime + 1; //이동 시간 1 더해줌
                } else { //현재 시간이 signalTime 이후라면 파란불이 지났으므로 다음 파란불을 기다려야 함
                    long wait = ((now.time - next.signalTime + m - 1) / m) * m; // 다음 파란불까지의 시간 계산
                    nextTime = wait + next.signalTime + 1; //이동 시간 계산
                }
								//더 짧은 시간으로 업데이트
                if (dist[next.to] > nextTime) {
                    dist[next.to] = nextTime;
                    pq.offer(new State(next.to, nextTime));
                }
            }
        }
    }

    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<>();
        for (int i = 0; i <= n; i++) {
            graph.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());

            graph.get(a).add(new Node(b, i));
            graph.get(b).add(new Node(a, i));
        }

        dist = new long[n + 1];
        Arrays.fill(dist, Long.MAX_VALUE);

        find();
        System.out.println(dist[n]);
    }
}