BOJ_24042 : 횡단보도

👉 문제링크

---

---

🔸 문제 분석 🔸

• N개의 지역과 M개의 횡단보도가 있다.
• 횡단보도는 입력 순서대로 0~M-1 초에 파란불이 켜져 건널 수 있다.
• 1번 지역부터 출발해 N번 지역에 도착할 수 있는 최단 시간을 출력한다.

🔸 문제 풀이 🔸

• N이 최대 10만, M이 최대 70만이므로 BFS로 최단시간을 구하면 시간초과가 난다. 따라서 Dijkstra(다익스트라) 알고리즘을 이용해 최단시간을 구한다.
• 현재 지역에서 갈 수 있는 다음 지역을 건널 때 걸리는 시간을 계산하고, 기록 된 소요 시간보다 작다면 업데이트한다.

🔸 코드 🔸

import java.io.*;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        ArrayList<Sign>[] adjList = new ArrayList[N + 1]; // 경로+시간
        long[] result = new long[N + 1]; // 최단 시간

        for (int i = 1; i <= N; i++) {
            adjList[i] = new ArrayList<>();
            result[i] = Long.MAX_VALUE;
        }

        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            adjList[A].add(new Sign(B, i));
            adjList[B].add(new Sign(A, i));
        }

        // Dijkstra
        Queue<Road> q = new PriorityQueue<>();
        q.add(new Road(1, 0L));
        result[1] = 0;

        while (!q.isEmpty()) {
            Road road = q.poll();
            if (road.time > result[road.site]) { // 이미 더 빠른 경우 처리함
                continue;
            }
            if (road.site == N) { // N 찾음
                break;
            }

            // 최단시간 업데이트
            for (Sign sign : adjList[road.site]) {

                int temp = (int) (road.time % M); // 현재 시간의 주기 위치

                if (temp <= sign.minT) { // 이번 주기에 이동
                    temp = sign.minT - temp; // 추가되는 시간
                } else { // 다음 주기에 이동
                    temp = sign.minT + M - temp; // 추가되는 시간
                }

                if (result[sign.site] > road.time + temp) { // 더 짧은 경우 찾음
                    result[sign.site] = road.time + temp; // 업데이트
                    q.add(new Road(sign.site, road.time + temp)); // 큐에도 넣기
                }
            }
        }

        // Output
        bw.write(Long.toString(result[N]));
        bw.flush();
    }

    private static class Sign {
        int site;
        int minT;

        public Sign(int site, int minT) {
            this.site = site;
            this.minT = minT;
        }
    }

    private static class Road implements Comparable<Road> {
        int site;
        long time;

        public Road(int site, long time) {
            this.site = site;
            this.time = time;
        }

        @Override
        public int compareTo(Road o) {
            return Long.compare(this.time, o.time);
        }
    }
}

🔸 코드 해석 🔸

• 각 횡단보도의 파란불이 켜지는 시간과 도착지를 저장하기 위해 Sign 클래스를 만들었다.
  • minT는 불이 켜지는 시간임과 동시에, 횡단보도 주기의 인덱스이다.
• 다익스트라 알고리즘을 위해 Road 클래스를 만들어 사용했다.
  • 현재 지역 번호와 도착하는데 걸린 시간을 저장한다.
  • 우선순위 큐에 넣기 위해 compareTo() 메서드도 오버라이딩했다.
• 경로와 시간을 Sign클래스를 인자로 갖는 ArrayList 배열 adjList를 사용했다.
  • 입력되는 경로를 양방향으로 저장한다.
  • 입력 인덱스를 minT로 저장한다.
• 최단시간을 저장할 long배열 result를 Long의 최댓값으로 초기화한다.
• 우선순위 큐 q에 Road 클래스를 인자로하고 다익스트라 알고리즘을 실행한다.
  • N을 찾을 때 까지 최단시간을 업데이트한다.
  • 현재 시간의 주기 인덱스를 구해, 다음 경로의 시간이 이번 주기인지 다음 주기인지 판단하고 추가 시간을 계산한다.
  • 이번 경로가 result에 저장 된 시간보다 짧다면, result 값을 업데이트하고 큐에 넣어 다시 탐색한다
• 최종 result[N]에 저장된 최소시간을 추력한다.

---

🔸 end 🔸

• 어려웠다. 처음에 시간초과가 날 것임을 알았지만 문제 이해도 너무 어렵고 혼란스러워서 BFS로 먼저 풀어보았다.
• 당연히 시간초과가 났고, 결국 알고리즘 태그를 보고 Dijkstra 알고리즘인걸 알고 다시 풀어서 총 1시간+1시간 = 2시간 소요로 풀어낼 수 있었다.
  • 횡단보도 주기인 M이 70만으로, 주기를 반복하다가 int를 넘을 수 있어 long으로 선언해야 했다.
  • 입력되는 경로를 주기 인덱스(시간)과 함께 저장하는게 생소했다.
• 좀 웃긴 얘기지만, 문제의 시간 조건이 틀린 줄 알고 오류 수정을 건의할 뻔 했다.
  • 파란불이 1초 ~ M초에 켜진다고 이해서, N=2일때 도착하면 1초가 아니라 2초가 아닌가? 싶었다.
  • 하지만 불이 켜지는 건 0초~M초였다. 문제를 풀고 나서도 이해를 잘 못했던 부분이 있는게 웃기고 반성하게 됐다...(글 쓰면서 다시 확인하다가 알게됐다. 쓰기전에 알아서 다행이다...)