[Boj_5214] 환승

📎 문제 링크

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

 

▸ 문제

아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 K개를 서로 연결한다. 1번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개일까?

 

▸ 입력

첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000)

다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어진다. 총 K개 숫자가 주어지며, 이 숫자는 그 하이퍼튜브가 서로 연결하는 역의 번호이다.

 

▸ 출력

첫째 줄에 1번역에서 N번역으로 가는데 방문하는 역의 개수의 최솟값을 출력한다. 만약, 갈 수 없다면 -1을 출력한다.

 

📍 문제 정보

• 🥇  문제 레벨 : 골드 2
• 🔔  문제 유형 : 그래프 이론, 그래프 탐색, 너비 우선 탐색
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

너비 우선 탐색(BFS)과 인접 리스트를 활용하여,

하이퍼 튜브를 환승역 개념으로 그래프를 구성하는 방식으로 해결할 수 있는 문제이다.

 

각 하이퍼 튜브는 k개의 역을 직접 연결하는 것이 아니라, 하이퍼 튜브 노드를 하나의 환승역으로 추가하여 각 역과 연결한다.

 

예제 입력 1을 그림으로 그려본다면 아래와 같다.

 

이렇게 하면, 하이퍼 튜브 노드를 지날 때는 이동 거리를 증가시키지 않고, 실제 역을 지날 때만 이동 거리를 증가시키는 방식으로 최단 경로를 구할 수 있다.

 

그림을 보면 알 수 있듯이, 실제 역끼리는 직접 연결되어 있지 않고, 하이퍼 튜브 노드와 역 노드끼리만 연결되어 있다.

따라서 1번 역에서 N번 역으로 이동할 때, 너비 우선 탐색을 수행하면 가장 먼저 도착한 노드가 최단 경로가 된다.

 

위 풀이를 코드로 작성해 보면 아래와 같다.

 

✔ 최종 코드

메모리 : 165668KB
시간 : 764ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int n, k, m;
    static ArrayList<ArrayList<Integer>> list;
    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()); // 하이퍼튜브 개수

        list = new ArrayList<>();
        // 1~n 역, n+1~m 하이퍼튜브
        for (int i = 0; i <= n+m; i++) {
            list.add(new ArrayList<>());
        }
        int hyperTube, node;
        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            hyperTube = n+i;
            for (int j = 0; j < k; j++) {
                node = Integer.parseInt(st.nextToken());
                list.get(node).add(hyperTube);
                list.get(hyperTube).add(node);
            }
        }

        int ans = bfs(1);

        System.out.println(ans);
    }

    private static int bfs(int start) {
        Queue<Integer> que = new LinkedList<>();
        int[] checked = new int[n+m+1]; // 거쳐간 횟수 기록

        que.offer(start);
        checked[start] = 1;

        while (!que.isEmpty()) {
            Integer now = que.poll();

            if (now == n) { // n번째 도착
                return checked[now];
            }

            for (Integer next : list.get(now)) {
                if (checked[next] == 0) { // 방문 X
                    // 하이퍼튜브 노드로 갈 땐 이동거리를 늘리지 않고, 
                    // 실제 노드로 갈 때에만 이동거리를 늘린다.
                    if (next <= n) { // 역
                        checked[next] = checked[now]+1;
                    } else { // 하이퍼튜브
                        checked[next] = checked[now];
                    }
                    que.offer(next);
                }
            }
        }

        return -1;
    }
}

 

추천받아 풀었던 문제인데, 최근에 다시 풀면서 그래프 문제 중에서도 신선하고 새로운 문제 같아서 포스팅해 본다 !
처음 풀 때, 아이디어가 떠오르지 않아 다른 사람의 아이디어를 참고하여 해결했던 기억이 있다.

그때 당시에는 풀이를 봐도 어렵다고 생각했는데, 이번에는 그때보다 순조롭게 문제를 해결할 수 있어 뿌듯했다. 😊⭐

 

 

 

 

 

📃 reference

• https://t-anb.tistory.com/17