골드에그

1. 문제요약

24042번: 횡단보도 (acmicpc.net)

횡단보도에 파란불이 들어오면 반대편 지역으로 이동할 수 있으며 이동하는 데 1분이 걸린다. 1 + i ( 0 <= i < M) 번째 신호는 i, M+i, 2M+i, 3M+i, ... 분 주기에 시작해서 1분 동안 Ai 번 지역과 Bi 번 지역을 잇는 횡단보도에 파란불이 들어오고, 다른 모든 횡단보도에는 빨간불이 들어온다. 한 주기 동안 같은 횡단보도에 파란불이 여러 번 들어올 수 있다.

횡단보도와 신호의 정보가 주어질 때, 시간 0 분에서 시작해서 1 번 지역에서 N 번 지역까지 가는 최소 시간을 구하시오.

2. 문제예제

3. 문제풀이(수동)

예제 풀이 2번을 수동 풀이한다.

각 횡단보도가 켜지는 시간대는 위 표와 같다. 내가 만약 7 - 8 번 구간을 처음에 선택하였다면 그 다음 구간을 선택할 때 걸리는 시간이 시계방향처럼 연산된다. 그 다음 1 - 5 번 구간을 선택하면 +2 가 되고, 3 - 4 번 구간을 선택하면 한 바퀴 돌아서 +10 이 된다. 그 다음 구간의 시간 대가 현재 시간 대보다 적다면 한 바퀴 돌아서 연산된다.

그렇게 1번부터 8번까지 순회하는 길이 가장 빠른 구간은 다음과 같다.

1 - 2 >> 2 - 3 >> 3 - 4 >> 4 - 8 로 7 + 2 + 4 + 5 = 18 이다.

4. 팩트추출

Fact 1 : 최소 시간이 소요되는 구간을 찾는 문제로 다이젝스트라 알고리즘 문제다. 다만 일반적인 다이젝스트라와 다른 점은 거리 계산 시 그 다음 구간의 시간 대가 현재 시간 대보다 작으면 cost 값을 한 바퀴 돌아서 더해주어야 한다는 점이다.

5. 문제전략

다이젝스트라 응용 문제다.

6. 소스코드

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

public class Main {
    private static int N, M;
    private static List<List<Node>> crossWalk;
    private static long[] distance;
    static class Node implements Comparable<Node>{
        int index;
        long cost;
        Node(int index, long cost) {
            this.index = index;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node o) {
            return Long.compare(this.cost, o.cost);
        }
    }
    private static void dijkstra() {
        PriorityQueue<Node> queue = new PriorityQueue<>();
        queue.offer(new Node(1, 0));
        distance[1] = 0;

        while(!queue.isEmpty()) {
            Node currentNode = queue.poll();
            if (currentNode.cost > distance[currentNode.index])
                continue;
            for (Node next :crossWalk.get(currentNode.index)) {
                int nextIndex = next.index;
                long nextCost;
                if (currentNode.cost <= next.cost) {
                    nextCost = next.cost + 1;
                } else {
                    // 모듈러 연산
                    nextCost = ((long) Math.ceil(((double)currentNode.cost-next.cost)/M)) * M + next.cost + 1;
                }
                if (nextCost < distance[nextIndex]) {
                    distance[nextIndex] = nextCost;
                    queue.offer(new Node(nextIndex, nextCost));
                }
            }
        }
    }
    public static void main(String[] args) throws Exception {
        StringTokenizer st;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

        crossWalk = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            crossWalk.add(new ArrayList<Node>());
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            crossWalk.get(u).add(new Node(v, i));
            crossWalk.get(v).add(new Node(u, i));
        }
        dijkstra();
        System.out.println(distance[N]);
    }
}