[ 백준 2021 / Java ] 최소 환승 경로

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

2021번: 최소 환승 경로

 

문제

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

입력

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

출력

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

예제 입력 1 복사

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

예제 출력 1 복사

2

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    static class Node {
        int to, count;
 
        public Node(int to, int count) {
            this.to = to;
            this.count = count;
        }
    }
    
    static int N, L, S, E;
    static List<Integer>[] routes, edges;
 
    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
           BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken()); //역의 개수
            L = Integer.parseInt(st.nextToken()); //노선의 개수
            routes = new ArrayList[L + 1]; //routes[i]:i번째 경로에 속한 역들의 집합
            edges = new ArrayList[N + 1]; //edges[i]:i번 역이 갈 수 있는 routes들의 집합
            for (int i = 0; i <= L; ++i) routes[i] = new ArrayList<>();
            for (int i = 0; i <= N; ++i) edges[i] = new ArrayList<>();
            for (int i = 1; i <= L; ++i) {
                String[] str = br.readLine().split(" ");
                for (int j = 0; j < str.length - 1; ++j) {
                    int station = Integer.parseInt(str[j]);
                    routes[i].add(station);
                    edges[station].add(i);
                }
            }
            st = new StringTokenizer(br.readLine());
            S = Integer.parseInt(st.nextToken()); //출발지
            E = Integer.parseInt(st.nextToken()); //도착지
            bw.write(bfs() + "\n");
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    
    public static int bfs() {
        boolean[] visitRoute = new boolean[L + 1]; //route 방문 체크
        boolean[] visitStation = new boolean[N + 1]; //station 방문 체크
        
        Queue<Node> q = new LinkedList<>();
        visitStation[S] = true;
        for (int v : edges[S]) {
            visitRoute[v] = true;
            q.offer(new Node(v, 0));
        }
        
        while (!q.isEmpty()) {
            Node n = q.poll();
            for (int v : routes[n.to]) {
                if (v == E) return n.count;
                if (visitStation[v]) continue;
                visitStation[v] = true;
                for (int nv : edges[v]) {
                    if (visitRoute[nv]) continue;
                    visitRoute[nv] = true;
                    q.offer(new Node(nv, n.count + 1));
                }
            }
        }
        return -1;
    }
}