[Java] 백준 5214번 - 환승

[문제]

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

5214번: 환승

[풀이]

BFS(너비 우선 탐색)을 이용하여 풀이하였습니다.

 

입력으로 들어오는 숫자들을 2개로 나누어 생각하였습니다.

tubeOut 각 하이프튜브가 이동할 수 있는 역 번호

tubeIn 각 역들이 이동할 수 잇는 하이프튜브 번호

 

따라서 예시 1번을 사용하면 tubeOut과 tubeIn는 아래와 같이 구성됩니다.

두 ArrayList를 활용해서 findStation()를 통해 BFS를 진행하면,

 

( 이때 N = 1이라면 무저건 1번만에 역에 이동 가능하다는 예외 처리를 하지 못해 100%에서 오답처리가 되는 문제가 발생했었습니다. )

 

1번 역 -> 2,3튜브로 이동 가능 (  1번 이동 )

2번 역 -> 1번튜브는 이미 방문했으니 continue

3번역 ->  3번 튜브로 이동 가능 ( 2번 이동 )

 

3번 튜브 -> 3, 6, 7번 역으로 이동 가능

3번 역 -> 이미 방문 했으니 continue

6번 역 -> 4, 5 튜브로 이동 가능 ( 3번 이동 )

5번 튜브에 N의값 9가 있으므로  ( 4번 이동 ) 4를 출력합니다.

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Station implements Comparable<Station>{
    int index;
    int sum;
    public Station(int index, int sum) {
        this.index = index;
        this.sum = sum;
    }

    @Override
    public int compareTo(Station o) {
        return this.sum - o.sum;
    }
}

public class Main {
    public static int N; // 역의 개수
    public static int K; // 한 하이퍼튜브가 연결하는 역의 개수
    public static int M; // 하이퍼튜브의 개수
    public static ArrayList<ArrayList<Integer>> tubeOut = new ArrayList<>(); // 각 튜브가 갈 수 있는 역 저장
    public static ArrayList<ArrayList<Integer>> tubeIn = new ArrayList<>(); // 각 역이 갈 수있는 튜브 저장
    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());

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

        tubeOut.add(new ArrayList<Integer>());
        for(int i=1;i<=M;i++) {
            tubeOut.add(new ArrayList<Integer>());
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<K;j++) {
                int num = Integer.parseInt(st.nextToken());
                tubeOut.get(i).add(num);
                tubeIn.get(num).add(i);
            }
        }
        findStation();
    }
    public static void findStation() {
        if(N == 1) {
            System.out.println(1);
            return;
        }
        
        PriorityQueue<Station> pq = new PriorityQueue<>();
        pq.offer(new Station(1, 1));

        boolean[] visitTube = new boolean[M + 1];
        boolean[] visitStation = new boolean[N + 1];

        while(!pq.isEmpty()) {
            Station p = pq.poll();
            visitStation[p.index] = true;
            for(Integer tube:tubeIn.get(p.index)) {
                if(visitTube[tube]) {
                    continue;
                }
                visitTube[tube] = true;
                for(Integer station:tubeOut.get(tube)) {
                    if(!visitStation[station]) {
                        visitStation[station] = true;
                        if(station == N) {
                            System.out.println(p.sum + 1);
                            return;
                        }
                        pq.offer(new Station(station, p.sum + 1));
                    }
                }
            }
        }
        System.out.println(-1);
    }
}