5214번

5214번 - 환승

처음에 V의 값이 꽤나 크긴 했지만, vector 를 이용한 연결리스트로 bfs를 구현하면 될 줄 알았다.

하지만 처음에는 중복값이 연결리스트에 들어왔고, 그래서 풀지 못했다.

그래서 인접 행렬을 이용해서 풀었더니 메모리 초과가 발생했다.

그래서 그 다음에는 map 을 이용해서 간선의 중복을 없애고 풀었지만, 시간초과가 발생했다.

그래서 다른 분들 풀이를 보니, 너무나 쉽지만 생각지 못했던,

하이퍼 튜브를 정점으로 만들어서 연결해주는 방법을 사용했다.

(기존 노드 말고 새로운 더미 노드를 생각해내는 방법을 잊지말자!) 

그렇게 문제를 풀게 되면 하이퍼 튜브를 거쳐 가기 때문에, 한 정점에서 다른 정점으로 이동하는데 2만큼이 필요하게 된다.

그래서 마지막 답을 구할 때, 최단 거리를 2로 나눠주고, 

정답은 간선의 최단 거리가 아니라 정점 노드의 최소 갯수이기 때문에 그 값에 + 1을 해주면 된다.

( N 개의 노드를 지나는 최단거리 간선은 N-1 개가 되기 때문에)

<정답 코드>

#include<iostream>
#include<vector>
#include<queue>
#include<map>
using namespace std;
 
int main()
{
    //freopen("input.txt", "r", stdin);
    int n, k, m;
    scanf("%d %d %d", &n, &k, &m);
    vector<vector<int>> v(n + 2000);
    
 
    int pos = n + 2;
    while (m--)
    {
        for (int i = 0; i < k; i++)
        {
            int tmp;
            scanf("%d", &tmp);
            v[pos].push_back(tmp);
            v[tmp].push_back(pos);
        }
        pos++;
    }
 
    vector<int> dist(n + 2000, -1);
    int start = 1;
    dist[start] = 0;
    queue<int> q;
    q.push(start);
 
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
 
        for (int i = 0; i <v[now].size(); i++)
        {
            int next = v[now][i];
 
            if (dist[next] == -1)
            {
                dist[next] = dist[now] + 1;
                q.push(next);
            }
        }
    }
 
 
    if (dist[n] == -1)
    {
        printf("-1\n");
    }
    else
    {
        printf("%d\n", dist[n]/2 + 1);
    }
 
    return 0;
}