[백준 5214] 환승 (JAVA)

문제

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

풀이

BFS를 이용하여 해결할 수 있습니다. 우선순위 큐를 이용하여 환승을 가장 적게 한 상태부터 꺼냅니다. 다른 호선을 탈 때 환승 카운트를 증가시킵니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static int N, K, M;
    public static ArrayList<Integer>[] transferStation;
    public static HashSet<Integer> destStation;
    public static ArrayList<Integer>[] line;

    public static void main(String[] args) throws IOException {

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

    public static int bfs() {

        if (N == 1) return 1;
        boolean[] visited = new boolean[M + 1];
        Queue<Integer> q = new LinkedList<>();
        for (int num : transferStation[1]) {
            q.offer(num);
            visited[num] = true;
        }
        transferStation[1].clear();

        int hop = 1;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int s = 0; s < size; s++) {
                int poll = q.poll();
                if (destStation.contains(poll)) {
                    return hop + 1;
                }

                // 호선에 있는 역
                for (int num : line[poll]) {
                    // 역을 방문안했으면
                    if (!transferStation[num].isEmpty()) {
                        // 그 역에 연결된 호선
                        for (int i : transferStation[num]) {
                            if (!visited[i]) {
                                visited[i] = true;
                                q.offer(i);
                            }
                        }
                        transferStation[num].clear();
                    }
                }
            }
            hop++;
        }

        return -1;
    }

    public static void makeHipertube() 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());

        destStation = new HashSet<>();
        line = new ArrayList[M + 1];
        transferStation = new ArrayList[N + 1];
        for (int i = 0; i <= N; i++) {
            transferStation[i] = new ArrayList<>();
        }

        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            line[i] = new ArrayList<>();
            for (int j = 0; j < K; j++) {
                int num = Integer.parseInt(st.nextToken());

                transferStation[num].add(i);

                if (num == N) {
                    destStation.add(i);
                }
            }
        }

        for (int i = 0; i <= N; i++) {
            if (transferStation[i].size() > 1) {
                for (int t : transferStation[i]) {
                    line[t].add(i);
                }
            }
        }

        br.close();
    }
}