BOJ#2593 엘리베이터

BOJ#2593 엘리베이터

* 문제

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

* 풀이

다익스트라를 이용해서 풀었습니다.

처음에 그래프 모델링에서 당황했는데 아래와 같이 해보았습니다.

문제에 나와있는 예제에서

ArrayList<ArrayList<Integer>> elevator = new ArrayList<>();

elevator : 각 엘리베이터에서 갈 수 있는 층

엘리베이터 1번 : [4, 7, 10]

엘리베이터 2번 : [7, 12]

엘리베이터 3번 : [4, 8, 12]

ArrayList<ArrayList<Integer>> floor = new ArrayList<>();

floor : 각 층에서 탈 수 있는 엘리베이터

4층 : [1, 3]

7층 : [1, 2]

8층 : [ 3 ]

10층 : [ 1 ]

12층 : [2, 3]

그리고 정점을 각 층이 아닌 엘리베이터로 정하였습니다.

그리고 다익스트라를 통해

시작 엘리베이터(시작점)에서 모든 엘리베이터까지의 최단 거리를 구하였습니다.

* 나의 코드

https://github.com/stack07142/BOJ/blob/b78b69a882f5b94caf5e4f9fb8b2e399bbe1e528/BOJ%232593/src/Main.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    static final int MAX_VALUE = 1000000000;
    static int min = MAX_VALUE;

    public static void main(String[] args) throws IOException {

        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        // Graph Modeling
        ArrayList<ArrayList<Integer>> floor = new ArrayList<>();
        ArrayList<ArrayList<Integer>> elevator = new ArrayList<>();

        for (int i = 0; i < N + 1; i++) {

            floor.add(new ArrayList<>());
        }

        for (int i = 0; i < M + 1; i++) {

            elevator.add(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());

            while (X <= N) {

                floor.get(X).add(i); // 층 정보 : 각 층마다 탈 수 있는 엘레베이터
                elevator.get(i).add(X); // 엘레베이터 정보 : 엘레베이터마다 갈 수 있는 각 층

                X += Y;
            }
        }

        st = new StringTokenizer(br.readLine());

        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        // solve
        PriorityQueue<Node> pq = new PriorityQueue<>();

        int[] dist = new int[M + 1];
        int[] prev = new int[M + 1];
        Arrays.fill(dist, MAX_VALUE);

        for (int i = 0; i < floor.get(A).size(); i++) {

            pq.add(new Node(floor.get(A).get(i), 1));
            dist[floor.get(A).get(i)] = 1;
        }

        while (!pq.isEmpty()) {

            Node u = pq.poll();

            if (dist[u.elevator] < u.dist) continue;

            for (int i = 0; i < elevator.get(u.elevator).size(); i++) {

                int level = elevator.get(u.elevator).get(i);

                for (int j = 0; j < floor.get(level).size(); j++) {

                    int nextElevator = floor.get(level).get(j);

                    if (dist[nextElevator] > u.dist + 1) {

                        dist[nextElevator] = u.dist + 1;
                        prev[nextElevator] = u.elevator;

                        pq.add(new Node(nextElevator, dist[nextElevator]));
                    }
                }
            }
        }

        int lastElevator = 0;
        for (int i = 0; i < floor.get(B).size(); i++) {

            if (min > dist[floor.get(B).get(i)]) {

                min = dist[floor.get(B).get(i)];
                lastElevator = floor.get(B).get(i);
            }
        }

        if (min == MAX_VALUE) {

            System.out.println(-1);
        } else {

            System.out.println(min);
            print(prev, lastElevator);
        }
    } // ~main

    static void print(int[] prev, int elevator) {

        if (elevator == 0) return;
        print(prev, prev[elevator]);
        System.out.println(elevator);
    }
}

class Node implements Comparable<Node> {

    int elevator;
    int dist;

    Node(int elevator, int dist) {

        this.elevator = elevator;
        this.dist = dist;
    }

    @Override
    public int compareTo(Node o) {

        return this.dist < o.dist ? -1 : 1;
    }
}