✅ BFS ✅ 중복되는 간선 (메모리초과 문제 해결 방법)

문제

1. 해결 로직

하이퍼튜브가 1000개가 있고, 서로 연결하는 역의 갯수가 1000개가 있다면
약 1000 x 1000^2 개 즉, 1000^3개 만큼의 간선이 생긴다.
따라서 메모리 초과가 난다.

역들끼리 연결하게 되면 중복되는 간선이 많아지게 되고, 중복되는 간선들에 의해서 메모리초과가 발생하는 것이므로 하이퍼튜브를 하나의 정점 or 역으로 보고 풀면된다.

2. 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>

using namespace std;

int N, K, M;
int Cost[100001 + 1000];
vector<int> Station[100001 + 1000];

queue<pair<int, int> > que; // 역, 방문한 역의 개수
bool visited[100001 + 1000];

int BFS()
{
    que.push({1,1});
    Cost[1] = 1;
    visited[1] = true;
 
    while (!que.empty())
    {
        int now = que.front().first;
        int d = que.front().second;
        que.pop();
 
        if (now == N) return (d+1)/2;

        for (int i = 0; i < Station[now].size(); i++)
        {
            int next = Station[now][i];
            if(visited[next] == false){
                visited[next] = true;
                que.push({next,d+1});
            }
        }
    }
    return -1;
}

int main(){
    cin >> N >> K >> M;
    for (int i = 1; i <= M; i++)
    {
        for (int j = 0; j < K; j++)
        {
            int a; cin >> a;
            Station[a].push_back(i + N);
            Station[i + N].push_back(a);
        }
    }

    int ans = BFS();
    cout << ans << "\n";
}

3. 시간 복잡도

4. Review

보통은 시간초과가 많은데 이번문제는 특이하게도 메모리초과가 나는 문제이다.
하이퍼튜브를 하나의 역으로 보면 중복되는 간선이 없다는 아이디어가 중요했다.

5. Reference

https://yabmoons.tistory.com/260