[BOJ/Graph] 백준 5214 - 환승 (Java)

백준 5214 - 환승

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

문제

하이퍼튜브 하나는 역 K개를 서로 연결

입력
첫째 줄: 역의 수 N, 서로 연결하는 역의 개수 K, 하이퍼튜브 개수 M (1 <= N <= 100,000, 1 < K, M <= 1000)
M개 줄: 하이퍼튜브 정보/ 총 K개 숫자 - 하이퍼튜브가 서로 연결하는 역의 번호
출력: 1번역에서 N번역으로 가는데 방문하는 역의 개수 최솟값 / 갈 수 없다면 -1

---

풀이

• 역: 1 ~ N
• 하이퍼튜브: N + 1 ~ N + M
  
  • `int tube = N + i`

 

• `dist[i]`: 1번 역에서 i번 노드까지 최단 이동 횟수
  
  • `dist[i] = -1`: 아직 방문 X
  • `dist[1] = 1`: 1번 역은 1번 방문 처리

int[] dist = new int[N + M + 1];
Arrays.fill(dist, -1);
dist[1] = 1;

• `next > N`: 하이퍼튜브 노드로 이동할 때 => 횟수 증가 X
• 역으로 이동할 때(= 하이퍼튜브에서 내릴 때)만 횟수 + 1

for (int next : graph.get(cur)) {
    if (dist[next] == -1) {
        if (next > N) dist[next] = dist[cur];
        else dist[next] = dist[cur] + 1;

        q.offer(next);
    }
}

---

코드

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

// 환승
public class boj_5214 {
    static int N, K, M;
    static List<List<Integer>> graph;

    static int bfs() {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(1);

        int[] dist = new int[N + M + 1];
        Arrays.fill(dist, -1);
        dist[1] = 1;

        while (!q.isEmpty()) {
            int cur = q.poll();

            for (int next : graph.get(cur)) {
                if (dist[next] == -1) {
                    if (next > N) dist[next] = dist[cur];
                    else dist[next] = dist[cur] + 1;

                    q.offer(next);
                }
            }
        }

        return dist[N];
    }

    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());
        K = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        graph = new ArrayList<>();
        for (int i = 0; i <= N + M; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int tube = N + i;

            for (int j = 0; j < K; j++) {
                int station = Integer.parseInt(st.nextToken());

                graph.get(station).add(tube);
                graph.get(tube).add(station);
            }
        }

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