[백준 5214] 환승

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

5214번: 환승

느낌상 bfs를 사용해야 하는 것을 알겠으나

연결 그래프를 만들 때 모든 노드 각각에 대해 연결선을 만들면 시간 초과가 발생하는 문제이다.

 

이 때 사용하는 방법은 바로 더미노드를 만드는 것이다.

더미 노드를 만들어서 허브로 사용하여 노드를 연결한다.

 

1~n까지는 진짜 노드이고 n+1부터 더미 노드를 설정한다.

더미 노드의 경우 거리가 0으로 처리되게끔 한다.

/*
환승
가짜노드를 추가하는 bfs
*/
#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;
const int MAX = 100000;
int n, m, k;
vector<int> adj[MAX + 1001];
int visited[MAX + 1001];
int main(void)
{
  scanf("%d%d%d", &n, &m, &k);

  for (int i = 1; i <= k; i++)
  {
    for (int j = 0; j < m; j++)
    {
      int tmp;
      scanf("%d", &tmp);
      adj[n + i].push_back(tmp);
      adj[tmp].push_back(n + i);
    }
  }

  int result = -1;
  queue<int> q;
  q.push(1);
  visited[1] = 1;
  while (!q.empty())
  {
    int cn = q.front();

    //printf("cur node: %d level: %d\n", cn, cl);
    if (cn == n)
    {
      result = visited[cn];
      break;
    }
    q.pop();
    for (auto a : adj[cn])
    {
      if (visited[a] == 0)
      {
        if (a > n)
          visited[a] = visited[cn];
        else
          visited[a] = visited[cn] + 1;
        q.push(a);
      }
    }
  }

  printf("%d", result);

  return 0;
}