버스 노선으로 최단 경로 찾기: 그래프 변환의 힘

📖 문제 이해하기

이 문제는 복잡한 버스 시스템에서 최소한의 환승으로 목적지에 도달하는 방법을 찾는 것입니다. 각 버스는 정해진 노선을 무한히 반복하며, 우리는 출발지에서 목적지까지 가는데 필요한 최소 버스 수를 구해야 합니다.

예를 들어, routes = [[1,2,7],[3,6,7]]이고 source = 1, target = 6인 경우를 생각해봅시다. 첫 번째 버스는 1→2→7→1→2→7… 순서로 운행하고, 두 번째 버스는 3→6→7→3→6→7… 순서로 운행합니다. 버스 정류장 1에서 시작해서 6에 도달하려면, 첫 번째 버스를 타고 7번 정류장까지 간 다음, 두 번째 버스로 갈아타서 6번 정류장에 도착할 수 있습니다. 총 2대의 버스가 필요합니다.

이 문제에서 중요한 제약사항은 버스의 수가 최대 500개이고, 모든 노선의 총 정류장 수가 10<sup>5</sup>개를 넘지 않는다는 점입니다. 이는 알고리즘 설계에 중요한 힌트를 제공합니다.

🧠 첫 번째 시도와 그 한계점

가장 직관적인 접근법은 각 정류장을 노드로, 같은 버스로 연결된 정류장들을 간선으로 하는 그래프를 만드는 것입니다. 그리고 BFS를 사용해 출발지에서 목적지까지의 최단 경로를 찾는 방법을 생각할 수 있습니다.

하지만 이 방법에는 심각한 문제가 있습니다. 각 버스 노선에서 모든 정류장 쌍을 연결해야 하므로, 하나의 노선에 k개의 정류장이 있다면 k*(k-1)개의 간선이 필요합니다. 예를 들어, 100개의 정류장을 가진 노선이 있다면 거의 10,000개의 간선이 생성됩니다. 여러 노선이 있을 경우 간선의 수가 폭발적으로 증가하여 메모리와 시간 복잡도 모두에서 비효율적이 됩니다.

더 큰 문제는 이 방법으로는 “최소 버스 수”를 직접 추적하기 어렵다는 점입니다. 정류장 간의 거리를 세면 정류장 개수는 알 수 있지만, 실제로 몇 대의 버스를 탔는지 알기 어렵습니다.

💡 핵심 아이디어: 문제 공간의 변환

이 문제를 해결하는 핵심은 문제를 다른 관점에서 바라보는 것입니다. 정류장 중심이 아닌 버스 노선 중심으로 생각해보는 것이죠.

우리가 실제로 최소화하려는 것은 “환승 횟수”이므로, 각 버스 노선을 하나의 노드로 생각하고, 공통 정류장을 가진 노선들을 연결하는 그래프를 만들면 됩니다. 이렇게 하면 그래프에서의 최단 경로가 곧 최소 버스 수가 됩니다.

예를 들어, 노선 A가 [1,2,7]이고 노선 B가 [3,6,7]이라면, 두 노선은 정류장 7에서 만나므로 서로 연결됩니다. 이제 노선 A에서 노선 B로 가는 경로의 길이는 2가 되며, 이는 정확히 우리가 필요로 하는 버스의 수입니다.

이 접근법이 효과적인 이유는 버스 노선의 수가 최대 500개로 제한되어 있기 때문입니다. 정류장 수는 매우 클 수 있지만, 노선 수는 상대적으로 작으므로 노선 간의 연결 관계를 효율적으로 관리할 수 있습니다.

📘 그래프 변환 기법에 대하여
복잡한 문제를 해결할 때 가장 강력한 기법 중 하나는 문제 공간을 변환하는 것입니다. 원래 문제에서 다루기 어려운 객체들을 더 관리하기 쉬운 형태로 재구성함으로써, 기존 알고리즘을 효과적으로 적용할 수 있습니다. 이 경우, 정류장 중심의 복잡한 그래프를 노선 중심의 단순한 그래프로 변환했습니다.

🔍 알고리즘 상세 동작 과정

구체적인 예시로 알고리즘의 동작을 살펴보겠습니다. routes = [[1,2,7],[3,6,7],[4,5]], source = 1, target = 5인 경우를 가정해봅시다.

1단계: 정류장별 노선 매핑 먼저 각 정류장이 어떤 노선들에 포함되는지 매핑합니다.

  • 정류장 1: [노선 0]
  • 정류장 2: [노선 0]
  • 정류장 7: [노선 0, 노선 1]
  • 정류장 3: [노선 1]
  • 정류장 6: [노선 1]
  • 정류장 4: [노선 2]
  • 정류장 5: [노선 2]

2단계: 노선 간 연결 그래프 구성 공통 정류장을 가진 노선들을 연결합니다.

  • 노선 0과 노선 1: 정류장 7에서 연결
  • 노선 1과 노선 2: 연결 없음
  • 노선 0과 노선 2: 연결 없음

3단계: BFS 실행 출발지 1이 포함된 노선 0에서 시작하여 BFS를 수행합니다.

  • 초기: 노선 0의 거리 = 1 (첫 번째 버스)
  • 1회 확장: 노선 0에서 노선 1로, 노선 1의 거리 = 2 (두 번째 버스)
  • 노선 2는 다른 노선과 연결되어 있지 않으므로 도달 불가능

4단계: 결과 확인 목적지 5가 포함된 노선 2의 거리는 -1 (도달 불가능)이므로, 답은 -1입니다.

💻 소스 코드

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
        <em>// 출발지와 목적지가 같으면 버스가 필요 없음</em>
        if (source == target) return 0;
        
        <em>// 각 정류장이 포함된 노선들을 저장하는 맵</em>
        <em>// key: 정류장 번호, value: 해당 정류장을 지나는 노선들의 인덱스 리스트</em>
        unordered_map<int, vector<int>> mp;
        for (int i = 0; i < routes.size(); ++i) {
            for (auto & x : routes[i]) {
                mp[x].push_back(i);
            }
        }
        
        <em>// 노선 간의 연결 관계를 나타내는 그래프</em>
        <em>// G[i]는 노선 i와 직접 연결된 노선들의 집합 (공통 정류장을 가진 노선들)</em>
        unordered_set<int> G[501];
        for (int i = 0; i < routes.size(); ++i) {
            for (auto &x : routes[i]) {
                <em>// 정류장 x를 지나는 모든 노선들을 노선 i와 연결</em>
                for (auto & y : mp[x]) {
                    G[i].insert(y);
                }
            }
        }
        
        <em>// BFS를 위한 거리 배열 초기화</em>
        <em>// dist[i] = 노선 i에 도달하기 위해 필요한 최소 버스 수</em>
        <em>// -1은 아직 방문하지 않았음을 의미</em>
        vector<int> dist(routes.size()+1, -1);
        queue<int> q;
        
        <em>// 출발지를 포함하는 모든 노선을 시작점으로 설정</em>
        <em>// 이들 노선에는 첫 번째 버스로 바로 탈 수 있으므로 거리는 1</em>
        for (auto &x : mp[source]) {
            dist[x] = 1;
            q.push(x);
        }
        
        <em>// BFS 수행: 각 노선에서 연결된 다른 노선들로 확장</em>
        while(!q.empty()) {
            int curr_group = q.front();
            q.pop();
            
            <em>// 현재 노선과 연결된 모든 노선들을 확인</em>
            for (auto & x : G[curr_group]) {
                if (dist[x] == -1) {  <em>// 아직 방문하지 않은 노선이면</em>
                    <em>// 현재 노선까지의 거리 + 1 (환승 1회)</em>
                    dist[x] = dist[curr_group] + 1;
                    q.push(x);
                }
            }
        }
        
        <em>// 목적지를 포함하는 노선들 중에서 최소 거리 찾기</em>
        int ans = -1;
        for (auto & g : mp[target]) {
            if (dist[g] > 0) {  <em>// 도달 가능한 노선이면</em>
                if (ans == -1 || ans > dist[g]) {
                    ans = dist[g];
                }
            }
        }
        
        return ans;
    }
};

🔁 대안적 접근법

더 직관적이지만 비효율적인 방법으로는 각 정류장을 노드로 하는 전통적인 그래프를 만들고, 각 버스 노선 내의 모든 정류장 쌍을 연결하는 방법이 있습니다. 이 경우 BFS에서 각 간선의 가중치를 1로 두지 않고, 버스 환승 횟수를 추적하는 별도의 로직이 필요합니다.

하지만 이 방법은 앞서 언급했듯이 간선 수가 O(sum(route_length<sup>2</sup>))가 되어 메모리와 시간 복잡도 면에서 비효율적입니다. 현재 솔루션의 시간 복잡도는 O(N<sup>2</sup> + E)인데, 여기서 N은 노선 수, E는 총 정류장 수입니다.

📌 핵심 요약

이 문제의 핵심은 관점의 전환이었습니다. 정류장 중심의 복잡한 그래프를 노선 중심의 단순한 그래프로 변환함으로써, 복잡한 환승 문제를 표준적인 최단 경로 문제로 바꿀 수 있었습니다.

문제에서 버스 노선 수가 제한되어 있다는 제약사항이 이러한 변환을 가능하게 했고, BFS를 통해 효율적으로 해결할 수 있었습니다. 이는 복잡한 실제 문제를 해결할 때 문제 공간을 재구성하는 것이 얼마나 강력한 기법인지 보여주는 좋은 예시입니다.

Similar Posts