[백준] 5214번 : 환승[Java]

#풀이

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

public class Main {
    static int N,K,M;
    static ArrayList<Integer>[] graph;
    static int[] dist;
    static boolean[] visited;

    public static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;
        dist[start] = 1;

        while (!queue.isEmpty()) {
            int now = queue.poll();
            for (int next : graph[now]) {
                if (!visited[next]) {
                    visited[next] = true;
                    if(next<=N)dist[next] = dist[now] + 1;
                    else dist[next] = dist[now];
                    queue.add(next);
                }
            }
        }
    }

    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[N+M+1];
        visited = new boolean[N+M+1];
        dist = new int[N + M+ 1];

        for (int i = 0; i < graph.length ; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = N+1; i <= N+M; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<K; j++){
                int n = Integer.parseInt(st.nextToken());
                graph[i].add(n);
                graph[n].add(i);
            }

        }

        bfs(1);
        if(dist[N]==0)System.out.println("-1");
        else System.out.println(dist[N]);


    }
}

#성능

#정리

모든 노드들에 대해 간선을 추가하면 시간초과가 나는 문제이다.

나는 하이퍼튜브를 중간 노드로 생각하고 풀었다.(N+1~N+M번 노드)

하이퍼튜브와 해당 튜브로 갈 수 있는 모든 노드를 간선으로 연결하면 역->하이퍼튜브->역 꼴로 이동할 수 있다.

이때 역->하이퍼튜브 에서는 dist를 증가시키지 않고 하이퍼튜브->역 으로 이동하는 경우에만 dist를 증가시키면 역에서 역까지의 거리를 정확히 계산 할 수 있다.

이 문제는 거리가 아닌 지나친 역의 수이기 때문에 dist초기값을 1(출발역)으로 설정하고 풀었다.