[백준 5214] 환승

문제 링크 : https://www.acmicpc.net/problem/5214

이 문제는 bfs를 이용하여 풀 수 있습니다. 처음 백트래킹을 이용해서 문제를 접근하려고 하였으나 인접 리스트를 이용해서 그래프를 생성할 때 시간 초과가 발생하기 때문에 다른 방법을 찾아봐야 했습니다.

이 문제는 bfs를 단순히 적용하는 문제가 아닙니다. 만약 모든 역의 정보를 하나하나 추가한다면 N이 10만이기 때문에 인접 행렬 방식은 N^2, 인접 리스트 방식은 NxK^2로 탐색하는 과정에서 시간 초과가 발생합니다.

이 문제의 핵심은 "역과 역을 연결하는 것"이 아니라 "역과 역 사이에 하이퍼튜브를 두어 하이퍼튜브를 매개로 탐색하기"입니다. 즉 인접 행렬이나 리스트를 직접 만드는 것이 아니라 하이퍼튜브를 기준으로 하이퍼튜브에 연결된 역들의 인접 리스트를 만들고, 탐색하는 과정에서 역은 하이퍼튜브로 이동하고, 하이퍼튜브에서 이동 가능한 역으로 이동하는 방식으로 다음 역을 탐색합니다.

이 과정에서 최소 거리를 구하기 위해 bfs를 사용하며, 하이퍼튜브에 방문했을 경우 실제로 이동한 거리가 아니기 때문에 cnt값을 증가시키지 않고 큐에 추가하여 진행합니다.

다음은 코드입니다.

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

class Main{
    static int N,K,M,res=-1;
    static ArrayList<Integer>[] stations;
    static boolean[] check;

    public static void main(String[] args) throws Exception{
        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());

        // "역 - 하이퍼튜브 - 역" 이런 방식으로 역을 탐색하기 위해 하나의 1차원 리스트에 역과 하이퍼튜브를 모두 추가
        stations = new ArrayList[N+M+1];
        for(int i=0;i<stations.length;i++) stations[i] = new ArrayList<>();
        for(int i=1;i<=M;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<K;j++){
                int curr = Integer.parseInt(st.nextToken());
                stations[curr].add(N+i);
                stations[N+i].add(curr);
            }
        }

        check = new boolean[N+M+1];
        bfs();
        System.out.println(res);
    }

    static void bfs(){
        check[1] = true;
        Queue<Person> queue = new LinkedList<>();
        queue.add(new Person(1,1));

        while(!queue.isEmpty()){
            Person curr = queue.poll();

            if(curr.pos == N){
                res = curr.cnt;
                return;
            }

            ArrayList<Integer> currStation = stations[curr.pos];
            for(int i=0;i<currStation.size();i++){
                int next = currStation.get(i);

                if(!check[next]){
                    check[next] = true;
                    // 하이퍼튜브일 경우 카운트를 늘리지 않음
                    if(next > N) queue.add(new Person(next,curr.cnt));
                    // 역일 경우 카운트 늘리기
                    else queue.add(new Person(next,curr.cnt+1));
                }
            }
        }
    }

    static class Person{
        int pos;
        int cnt;

        Person(int pos, int cnt){
            this.pos = pos;
            this.cnt = cnt;
        }
    }
}