bfs응용1 [백준 5214] 환승 https://www.acmicpc.net/problem/5214 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 느낌상 bfs를 사용해야 하는 것을 알겠으나 연결 그래프를 만들 때 모든 노드 각각에 대해 연결선을 만들면 시간 초과가 발생하는 문제이다. 이 때 사용하는 방법은 바로 더미노드를 만드는 것이다. 더미 노드를 만들어서 허브로 사용하여 노드를 연결한다. 1~n까지는 진짜 노드이고 n+1부터 더미 노드를 설정한다. 더미 노드의 경우 거리가 0으로 처리되게끔 한다. /* 환승 .. 2021. 7. 5. 이전 1 다음