[BaekJoon] 24042 횡단보도 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int areaNum;
    static int period;
    static Map<Integer, List<Crosswalk>> crosswalks; // 한 지역에서 다른 지역으로 가는 횡단보도 정보

    static void input() {
        Reader scanner = new Reader();

        areaNum = scanner.nextInt();
        period = scanner.nextInt();
        crosswalks = new HashMap<>();
        for(int area = 1; area <= areaNum; area++) {
            crosswalks.put(area, new ArrayList<>());
        }

        // 횡단보도 정보를 입력받아 key는 횡단보도의 시작 지역으로, value는 (도착 지역, 주기에서 파란불이 들어오는 순서)들로 하여
        // crosswalks에 정보를 저장한다
        for(int count = 0; count < period; count++) {
            int area1 = scanner.nextInt();
            int area2 = scanner.nextInt();

            crosswalks.get(area1).add(new Crosswalk(area2, count));
            crosswalks.get(area2).add(new Crosswalk(area1, count));
        }
    }

    static void solution() {
        // 다익스트라 알고리즘을 통해 1번 지역에서 N번 지역까지 가는 최소 시간을 구한다
        System.out.println(dijkstra(1));
    }

    static long dijkstra(int start) {
        PriorityQueue<Crosswalk> queue = new PriorityQueue<>();
        long[] weights = new long[areaNum + 1]; // 각 지역까지 가는데에 필요한 최소 시간
        Arrays.fill(weights, Long.MAX_VALUE);

        queue.offer(new Crosswalk(start, 0));
        weights[start] = 0;

        while (!queue.isEmpty()) {
            Crosswalk cur = queue.poll();

            if (cur.area == areaNum) { // N번 지역에 도착했다면
                // 그때까지 걸린 시간을 반환한다
                //  - PriorityQueue를 이용하여 이동한 시간 오름차순으로 정령되도록 하였으므로
                //  - 가장 처음 N번 지역에 도착한 경우가 최소 시간으로 N번 지역까지 간 경우가 된다
                return cur.weight;
            }
            if (weights[cur.area] < cur.weight) { // 이전까지 구한 현재 지역까지 이동하기 위한 최소 시간보다 현재 이동한 시간이 더 길다면
                // 최소 시간이 될 수 없으니 다음 경우를 확인한다
                continue;
            }

            // 현재 지역에서 이동할 수 있는 횡단보도를 순회하며 다음 지역으로 이동할 수 있는 경우 이동하여 N번 지역까지 이동했을 때 필요한 최소 시간을 구한다
            for(Crosswalk next : crosswalks.get(cur.area)) {
                int nextArea = next.area;
                // 현재 시간에 따라 가중치가 달라지기 때문에 현재 시간에 따라 가중치를 구한다
                long nextWeight = getNextWeight(next.weight, cur.weight) + 1;

                // 다음 위치까지 이전까지 구한 최소 시간이 현재 이동하는 시간보다 크다면 값을 갱신하고 queue에 넣어 다음 탐색 시에 이용한다
                if(weights[nextArea] > nextWeight) {
                    weights[nextArea] = nextWeight;
                    queue.offer(new Crosswalk(nextArea, nextWeight));
                }
            }
        }

        return Integer.MAX_VALUE;
    }

    static long getNextWeight(long nextWeight, long curWeight) {
        // 아직 1주기를 돌지 않았고 현재 시간 이상에서 횡단보도 파란불이 들어오는 경우
        // 그 차이만큼이 다음 횡단보도 파란불이 들어오는 시간이다
        // 이 시간에 현재까지 이동한 시간을 더하여 다음 시간을 구한다
        if(nextWeight >= curWeight) {
            return (nextWeight - curWeight) + curWeight;
        }

        // 1주기 이상 돌았거나 현재 시간 이전에 횡단보도 파란불이 들어오는 경우
        // 우선 현재 시간이 주기에서 몇 번째에 해당하는지 구한다
        // 이후에는 이전처럼 현재 주기 이상에서 횡단보도 파란불이 들어오는 경우와 아닌 경우로 나누어 시간을 구한다
        //  - 이상에서 들어오는 경우 : 이전과 똑같이 구한다
        //  - 이하에서 들어오는 경우 : (주기 + (다음 횡단보도 주기 - 현재 시간 주기) + 현재까지 이동한 시간)을 이용하여 시간을 구한다
        long curPeriod = curWeight % period;
        if(nextWeight >= curPeriod) {
            return (nextWeight - curPeriod) + curWeight;
        } else {
            return (period + (nextWeight - curPeriod)) + curWeight;
        }
    }

    static class Crosswalk implements Comparable<Crosswalk> {
        int area;
        long weight;

        public Crosswalk(int area, long weight) {
            this.area = area;
            this.weight = weight;
        }

        @Override
        public int compareTo(Crosswalk o) {
            if(weight < o.weight) return -1;
            else if(weight > o.weight) return 1;
            return 0;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}