[Java] 백준 23030. 후다다닥을 이겨 츄르를 받자!

📌 문제 링크 - https://www.acmicpc.net/problem/23030

 

---

 

 

 

문제

쿠기는 평소 지하철 최단 경로를 탐색하여 소요 시간을 알려주는 '후다다닥' 어플을 사용 중이다. 그러나 쿠기는 걸음이 너무 느려서 '후다다닥'이 알려주는 경로를 따라가면 항상 지하철이 떠나간 빈 플랫폼을 맞이해야 했다.

허탈한 마음에 속상해하던 쿠기는 때마침 창업경진대회가 열린다는 소식을 들었다. 쿠기는 환승 시간과 출발지, 도착지를 입력하면 최단 경로로 이동했을 때 걸리는 소요 시간을 알려주는 어플을 만들어 출품하기로 결심했다.

쿠기가 사는 도시의 지하철 노선은 총 N개가 있으며 1~N까지의 번호로 노선을 구분한다. 각 노선에는 최소 1개, 최대 50개의 역이 있다. 노선에 속한 역에는 가장 왼쪽 끝에 위치한 역을 1번으로 하여 1씩 증가하는 번호가 주어진다. 역 번호가 1씩 차이나는 두 역은 인접하다고 말할 수 있다. 하나의 역에서 인접한 역사이의 거리는 일정하여 지하철을 통해 이동하는 데 모두 1만큼의 시간이 걸린다. 지하철은 양방향 모두 통행이 가능하며, 지하철의 방향을 바꿔타는 시간과 지하철을 타기 위해 대기하는 시간은 걸리지 않는다.

쿠기가 사는 도시의 지하철에는 M개의 환승역이 존재한다. 두 개의 노선이 하나의 역에서 만나는 지점을 환승역이라고 한다. 환승역에 3개 이상의 노선이 겹치는 일은 존재하지 않는다. 환승을 하는 경우 걸어서 이동해야 하므로 사용자는 각자 자신이 환승을 하는 데 걸리는 시간 T를 입력한다. 모든 환승역에서 걸어야 하는 거리는 동일하며, 모든 요청에 대해 항상 도착할 수 있다.

하지만 쿠기는 프로그래밍을 할 줄 모르기 때문에 츄르 100개를 걸고 대신 코드를 짜줄 사람을 찾고 있다.

 

맛있는 츄르를 얻어보자. 사용자가 환승 시간 T와 출발지, 도착지를 입력하면 최단 경로로 이동하였을 때 걸리는 소요 시간을 알려주는 프로그램을 만들어야 한다.

 

입력

첫째 줄에 노선의 개수 N(2 ≤ N ≤ 10)이 주어진다.

둘째 줄에 N개의 노선별로 속한 역의 개수가 차례로 주어진다. (1 ≤ 역의 수 ≤ 50)

셋째 줄에 환승역의 개수 M(1 ≤ M ≤ ⌊모든 역의 수 / 2⌋)이 주어진다.

넷째 줄부터 M개의 줄에 환승역의 정보가 주어진다.

각 줄은 네개의 양의 정수 P1, P2, Q1, Q2로 구성되며 P1번 노선의 P2역과 Q1번 노선의 Q2역이 연결된 환승역이라는 것이다. 이미 환승역으로 주어진 역은 중복되게 주어지지 않는다.

그 다음 줄에는 사용자의 요청 개수 K(1 ≤ K ≤ 1,000)가 주어진다.

이어서 K개의 줄에 걸쳐 5개의 양의 정수 T(0 ≤ T ≤ 1,000), U1, U2, V1, V2가 주어지며, 환승에 걸리는 소요 시간이 T이며 출발지는 U1번 노선의 U2역이고 도착지는 V1번 노선의 V2역이라는 뜻이다.

 

 

출력

각 사용자의 요청에 대하여 출발지에서 도착지로 가는 최단 시간을 한 줄에 하나씩 출력한다.

 

 

 

 

 

---

 

 

풀이

지하철 노선은 총 N개가 있으며 1~N까지의 번호로 노선을 구분한다. 각 노선에는 최소 1개, 최대 50개의 역이 있다.

각 역은 인접한 역으로 이동(이동 시간 1) 할 수 있으며, 환승역일 경우 환승(이동 시간 T) 할 수 있다.

 

역끼리 연결 정보를 구현하고 나면 나머지는 다익스트라로 풀 수 있는 문제다.

양방향 환승역 정보를 저장하기 위해 int형 배열을 사용해 준다. (한 환승역에는 두 개의 노선만 연결될 수 있으며, 세 개 이상의 노선이 만나는 일은 없다.)

// 넷째 줄부터 M개의 줄에 환승역의 정보가 주어진다.
for(int i=0; i<M; i++) {
    st = new StringTokenizer(br.readLine());
    // a1번 노선의 a2역과 b1번 노선의 b2역이 연결된 환승역이라는 것
    int a1 = Integer.parseInt(st.nextToken());
    int a2 = Integer.parseInt(st.nextToken());
    int b1 = Integer.parseInt(st.nextToken());
    int b2 = Integer.parseInt(st.nextToken());

    // 환승역 설정 (BASE = 100)
    int a = a1 * BASE + a2;
    int b = b1 * BASE + b2;

    transfer[a] = b;
    transfer[b] = a;
}

위의 코드와 같이 a역에서는 b역을 갈 수 있고, b역에서는 a역을 갈 수 있음을 저장해 준다.

이때 효율적으로 구현하기 위해 각 역을 (노선 * 100 + 역)과 같이 노선과 역을 하나의 고유한 정수로 관리한다. 예를 들어 1번 노선의 5번 역은 105역, 2번 노선의 4번 역은 204로 표현된다. transfer[105] = 204, transfer[204] = 105와 같이 설정할 수 있다.

 

이후 사용자의 요청에 따라 출발역과 도착역, 환승 시간 정보를 바탕으로 다익스트라로 탐색하여 각 요청에 대한 최소 시간을 구해주면 된다.

 

 

---

 

 

코드

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

// https://www.acmicpc.net/problem/23030
public class Main_23030 {
    private static final int MAX = 987654321, L = 1000, S = 50, BASE = 100;
    private static final int TOTAL = L + S + 1;
    private static final int[] D = {-1, 1}; // 인접한 역 이동 방향
    private static int[] transfer; // 환승정보
    private static int[] stationCnt; // 노선별로 속한 역의 개수
    private static Request[] requests; // 사용자의 요청


    public static void main(String[] args) throws IOException {
        init();
        sol();
    }//main


    private static void sol() {
        StringBuilder ans = new StringBuilder();
        int minTime;

        // 각 사용자의 요청에 대하여 출발지에서 도착지로 가는 최단 시간을 한 줄에 하나씩 출력
        for(Request request : requests) {
            minTime = getMinTime(request); // 최단 시간
            ans.append(minTime).append('\n');
        }

        System.out.print(ans);
    }//sol


    private static int getMinTime(Request request) {
        PriorityQueue<Station> pq = new PriorityQueue<>();
        int[] visited = new int[TOTAL];
        int transferTime = request.time; // 환승시간
        int cur = request.start; // 현재역
        int end = request.end; // 도착역
        int time = 0; // 소요시간

        Arrays.fill(visited, MAX);

        pq.offer(new Station(cur, time));
        visited[cur] = time;

        Station station;
        while(!pq.isEmpty()) {
            station = pq.poll();
            cur = station.station;
            time = station.time;

            if(visited[cur] < time) continue;
            if(cur == end) return time;

            // 인접한 역 이동 (이동 시간 1)
            for(int i=0; i<2; i++) {
                int next = cur + D[i]; // 다음역
                if(isAvailable(cur, next) && visited[next] > time + 1) {
                    visited[next] = time + 1;
                    pq.offer(new Station(next, time + 1));
                }
            }

            // 환승역일 경우 환승 (이동 시간 transferTime)
            if(transfer[cur] != 0) {
                int next = transfer[cur]; // 다음역
                if(visited[next] > time + transferTime) {
                    visited[next] = time + transferTime;
                    pq.offer(new Station(next, time + transferTime));
                }
            }
        }

        return visited[end];
    }//getMinTime


    private static boolean isAvailable(int cur, int next) {
        int curLine = cur / BASE;
        int nextLine = next / BASE;
        int nextStation = next % BASE;

        return curLine == nextLine && nextStation > 0 && nextStation <= stationCnt[nextLine];
    }//isAvailable


    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 첫째 줄에 노선의 개수 N(2 ≤ N ≤ 10)이 주어진다.
        int N = Integer.parseInt(br.readLine());

        transfer = new int[TOTAL]; // 환승정보
        stationCnt = new int[N+1]; // 노선별로 속한 역의 개수

        // 둘째 줄에 N개의 노선별로 속한 역의 개수가 차례로 주어진다. (1 ≤ 역의 수 ≤ 50)
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int line=1; line<=N; line++) {
            stationCnt[line] = Integer.parseInt(st.nextToken());
        }

        // 셋째 줄에 환승역의 개수 M(1 ≤ M ≤ ⌊모든 역의 수 / 2⌋)이 주어진다.
        int M = Integer.parseInt(br.readLine());

        // 넷째 줄부터 M개의 줄에 환승역의 정보가 주어진다.
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            // a1번 노선의 a2역과 b1번 노선의 b2역이 연결된 환승역이라는 것
            int a1 = Integer.parseInt(st.nextToken());
            int a2 = Integer.parseInt(st.nextToken());
            int b1 = Integer.parseInt(st.nextToken());
            int b2 = Integer.parseInt(st.nextToken());

            // 환승역 설정
            int a = a1 * BASE + a2;
            int b = b1 * BASE + b2;

            transfer[a] = b;
            transfer[b] = a;
        }

        // 사용자의 요청 개수 K(1 ≤ K ≤ 1,000)가 주어진다.
        int K = Integer.parseInt(br.readLine());
        requests = new Request[K];

        // K개의 줄에 걸쳐 5개의 양의 정수 T(0 ≤ T ≤ 1,000), U1, U2, V1, V2가 주어짐
        for(int i=0; i<K; i++) {
            st = new StringTokenizer(br.readLine());
            // 환승 소요 시간 T, 출발지는 U1번 노선의 U2역이고 도착지는 V1번 노선의 V2역
            int t = Integer.parseInt(st.nextToken());
            int u1 = Integer.parseInt(st.nextToken());
            int u2 = Integer.parseInt(st.nextToken());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            requests[i] = new Request(t, u1 * BASE + u2, v1 * BASE + v2);
        }

        br.close();
    }//init


    private static class Station implements Comparable<Station>{
        int station; // 현재역
        int time; // 소요시간
        Station(int station, int time) {
            this.station = station;
            this.time = time;
        }

        @Override
        public int compareTo(Station s) {
            return this.time - s.time;
        }
    }//Station


    private static class Request {
        int time; // 환승에 걸리는 소요 시간
        int start; // 출발역
        int end; // 도착역
        Request(int time, int start, int end) {
            this.time = time;
            this.start = start;
            this.end = end;
        }
    }//Request


}//class