[백준] 횡단보도 24042번 (java)

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

 

풀이 방법

주기마다 횡단보도의 신호가 들어온다는 것이 신기했던 문제이다.

 

현재 위치에서 이동할 수 있는 지역을 계산해 주기 위해 현재 위치에 해당하는 신호가 언제 들어오는지 시간을 체크해 주어야 한다.

이를 시간적으로 빠르게 해 주기 위해 그래프의 인접 리스트에 저장할 때 불이 들어오는 시간도 저장해 주었다. (아니면 M시간을 계속 순회해야 함)

 

그리고 최단 시간 안에 이동해야 하므로 bfs와 우선순위 큐를 사용해서 가장 시간이 적은 것부터 방문해서 처리해 주었다.

 

다음 노드로 가기 위해 시간계산은 만약 (현재 시간 % m ) 보다 이동할 신호의 시간이 크다면 다음 시간을 

cur.time + (next.time - (cur.time % m)) + 1) 같이 구해주었고 (단순 차이만 더해주면 된다.)

만약 작다면 cur.time + (m - (cur.time % m) + next.time) + 1을 이용해 구해주었다. (다음 주기에 가능하므로)

 

 

아래 코드의 시간복잡도는 O((N + M) \log N) 이다.

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


public class P_24042 {

    static int n, m;
    static ArrayList<ArrayList<Light>> graph = new ArrayList<>();
    static int[] visited;
    static class Light {
        int idx;
        int time;
        Light(int idx, int time) {
            this.idx = idx;
            this.time = time;
        }
    }
    static class Node {
        int idx;
        long time;
        Node(int idx, long time) {
            this.idx = idx;
            this.time = time;
        }
    }

    public static long bfs() {
        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> Long.compare(o1.time, o2.time));
        pq.add(new Node(1, 0));
        while (!pq.isEmpty()) {
            Node cur = pq.poll();
            if (visited[cur.idx] == 1) {
                continue;
            }
            visited[cur.idx] = 1;
            if (cur.idx == n)  return cur.time;
            for (int i = 0;i < graph.get(cur.idx).size();i++) {
                Light next = graph.get(cur.idx).get(i);
                if (visited[next.idx] == 1) continue;
                if (cur.time % m <= next.time % m) {
                    pq.add(new Node(next.idx, cur.time + (next.time - (cur.time % m)) + 1));
                }
                else {
                    pq.add(new Node(next.idx, cur.time + (m - (cur.time % m) + next.time) + 1));
                }
            }
        }
        return -1;

    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        visited = new int[n+1];
        int a, b;
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            graph.get(a).add(new Light(b, i));
            graph.get(b).add(new Light(a, i));
        }

        System.out.println(bfs());
    }
}