[BOJ 5214] 환승 (Java, BFS)

 

 

---

문제 링크

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

5214번: 환승

---

풀이 

- 역의 수 N, 한 하이퍼 튜브가 서로 연결하는 역의 개수 K, 하이퍼 튜브의 개수 M이 주어짐 (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000)

- 시간복잡도 O(V + E)

 

실패* 

 처음에 연결한 역 번호를 가지는 하이퍼 튜브와 연결된 하이퍼 튜브 번호를 가진 역 노드를 생각해서 List 2개 선언하여 풀었는데 '시간초과' 발생 확인

 

아이디어*

 하이퍼 튜브 또한 노드라고 생각해서 인접 리스트에 담아서 조회하게 될 경우 기본적인 BFS 알고리즘 로직으로 처리 가능

(문제 설명에서 놓친 부분. 한 하이퍼 튜브가 서로 연결하는 역의 개수)

 

인접 리스트 크기 = new ArrayList[N + M + 2];

9 3 5  -- N : 역의 수, K : 하이퍼 튜브가 서로 연결하는 역의 수(*), M : 하이퍼 튜브의 개수
1 2 3  -- M개 라인 만큼 입력, 하이퍼 튜브 n + 1번은 1,2,3 연결  (노드 10번)
1 4 5  -- 하이퍼 튜브 n + 2번은 1,4,5 연결  (노드 11번)
3 6 7  -- 하이퍼 튜브 n + 3번은 3,6,7 연결  (노드 12번)
5 6 7
6 8 9

- HyperTube 또한 하나의 노드, 정점이라 생각하고 양방향 그래프 표현

- 그리고 1번 노드 ~ N 노드까지 방문처리 하면서 거리값 갱신 (이때 하이퍼 튜브 포함되어 거리 값이 갱신됨)

MultiSource BFS 사용하여 노드 번호와 거리값을 담음

- N에 도착할 경우 (하이퍼 튜브를 뺀) 역의 개수를 구해야 하므로 ( dist / 2 ) + 1 해줌

---

제출 코드

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

public class Main {
    
     static int N, K, M;

    static List<Integer>[] SUBWAY;

    static boolean[] VISIT; // 역의 거리

    static void input() 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()); // 하이퍼 튜브 개수

        VISIT = new boolean[N + M + 2];
        SUBWAY = new ArrayList[N + M + 2];

        // 하이퍼 튜브 (0번 제외)
        for(int i = 1; i <= (N+M+1); i++) SUBWAY[i] = new ArrayList<>();

        for(int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int hyperTube = N + i;
            for(int j = 1; j <= K; j++) {
                int value = Integer.parseInt(st.nextToken());
                SUBWAY[hyperTube].add(value);
                SUBWAY[value].add(hyperTube);
            }
        }
    }

    static void bfs(int start) {
        // MultiSource BFS 
        Queue<Integer> que = new LinkedList<>();
        que.add(start);
        que.add(0); // 초기 dist

        boolean find = false;
        while(!que.isEmpty()) {
            int x = que.poll(), dist = que.poll();
            if(x == N) {
                System.out.println((dist / 2) + 1);
                find = true;
                break;
            }

            for(int y : SUBWAY[x]) {
                if(VISIT[y]) continue;

                VISIT[y] = true;
                que.add(y);
                que.add(dist + 1);
            }
        }

        if(!find) System.out.println(-1);
    }

    static void pro() {
        bfs(1);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}