[백준5214] 환승

[백준5214] 환승

제한조건

시간 : 2초
메모리 : 256M

입력

첫 줄 : 역의 수 N, 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000)
다음 M개의 줄 : 하나의 하이퍼튜브에 연결된 역 번호

출력

1에서 출발하여 N에 도착하기 까지의 최소 방문역 수

자료구조

• Array, ArrayList, Deque

    static int N, K, M, i, j, k;
    static int[] visit_S;
    static boolean[] visit_T;
    static ArrayList<Integer>[] list_S, list_T;
    // queue in BFS
    Deque<Integer> q = new ArrayDeque<Integer>();

알고리즘

• BFS

    static int bfs(int here_S) {
        Deque<Integer> q = new ArrayDeque<Integer>();
        visit_S[here_S] = 1;
        q.offer(here_S);
        while (!q.isEmpty()) {
            here_S = q.poll();
            if (here_S == N)
                return visit_S[here_S];
            for (i = 0; i < list_S[here_S].size(); i++) {
                int here_T = list_S[here_S].get(i);
                if (!visit_T[here_T]) {
                    visit_T[here_T] = true;
                    for (j = 0; j < list_T[here_T].size(); j++) {
                        int next_S = list_T[here_T].get(j);
                        if (visit_S[next_S] == 0) {
                            visit_S[next_S] = visit_S[here_S] + 1;
                            q.offer(next_S);
                        }
                    }
                }
            }
        }
        return -1;
    }

풀이(java)

github#1