[ BOJ ][JAVA][2021] 최소 환승 경로

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

2021번: 최소 환승 경로

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	1537	323	180	21.352%

문제

어떤 도시의 지하철 노선에 대한 정보가 주어졌을 때, 출발지에서 목적지까지의 최소 환승 경로를 구하는 프로그램을 작성하시오. 실제 경로를 구할 필요는 없고, 환승 회수만을 구하면 된다.

입력

첫째 줄에 역의 개수 N(1≤N≤100,000), 노선의 개수 L(1≤L≤100,000)이 주어진다. 다음 L개의 줄에는 각 노선이 지나는 역이 순서대로 주어지며 각 줄의 마지막에는 -1이 주어진다. 마지막 줄에는 출발지 역의 번호와 목적지 역의 번호가 주어진다. 역 번호는 1부터 N까지의 정수로 표현된다. 각 노선의 길이의 합은 1,000,000을 넘지 않는다.

출력

첫째 줄에 최소 환승 회수를 출력한다. 불가능한 경우에는 -1을 출력한다.

예제 입력

10 3
1 2 3 4 5 -1
9 7 10 -1
7 6 3 8 -1
1 10

예제 출력

2

코드

/*
    최소환승경로
    BFS
*/
import java.io.*;
import java.util.*;

public class p2021 {
    static int n, l;
    static boolean[] visitedStat;
    static boolean[] visitedLine;
    static List<List<Integer>> stat; // 각 역에 어떤 노선을 포함하는지 담을 리스트
    static List<List<Integer>> line; // 노선에 어떤 역이 들어있는지 담을 리스트
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        l = Integer.parseInt(st.nextToken());

        visitedStat = new boolean[n + 1];
        visitedLine = new boolean[l + 1];

        stat = new ArrayList<>();
        line = new ArrayList<>();

        for (int i = 0; i <= n; i++) {
            stat.add(new ArrayList<>());
        }

        for (int i = 0; i <= l; i++) {
            line.add(new ArrayList<>());
        }

        for (int i = 1; i <= l; i++) {
            String[] s = br.readLine().split(" ");
            for (String station : s) {
                int num = Integer.parseInt(station);
                if (num != -1) {
                    line.get(i).add(num);
                    stat.get(num).add(i);
                }
            }
        }

        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        int answer = go(start, end);
        System.out.println(answer);
    }

    static int go(int start, int end) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        visitedStat[start] = true; // 출발역은 한번 도착했으므로 visit 처리
        for (int line : stat.get(start)) { // 출발역이 포함하고 있는 노선(line)들을 pq에 넣어준다. (ex. 1호선, 2호선 환승지점)
            pq.add(new Node(line, start, 0));
            visitedLine[line] = true; // 해당 노선들은 visit 처리
        }

        while (!pq.isEmpty()) {
            Node cur = pq.poll();
            if (cur.curStat == end) {
                return cur.cnt;
            }
            for (int nextStation : line.get(cur.curLine)) { // nextStation : 현재 노선에 포함되어 있는 다음 역들
                if (!visitedStat[nextStation]) {
                    visitedStat[nextStation] = true;
                    pq.add(new Node(cur.curLine, nextStation, cur.cnt));

                    for (int nextLine : stat.get(nextStation)) { // nextLine: 다음 역이 포함하고 있는 노선들
                        if (!visitedLine[nextLine]) {
                            visitedLine[nextLine] = true;
                            pq.add(new Node(nextLine, nextStation, cur.cnt + 1));
                        }
                    }
                }
            }
        }

        return -1;
    }

    static class Node implements Comparable<Node>{
        int curLine, curStat, cnt;

        public Node(int curLine, int curStat, int cnt) {
            this.curLine = curLine;
            this.curStat = curStat;
            this.cnt = cnt;
        }

        public int compareTo(Node o) {
            return cnt - o.cnt;
        }
    }
}