최단경로
-
[백준 BOJ/C++] 5214 환승알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 9. 2. 02:00
5214번: 환승 단순한 최단거리 탐색 문제로 보이지만 의외로 정답비율이 낮은편이고 헷갈릴 수 있는 부분이 있는 문제다. 하이퍼튜브라는 컨셉을 문제에서 의도한대로 머릿속에 그리는데 어려움이 있었다. 문제 설명은 아주 짧고 간단하다. K개의 역이 주어지고 이 중 1번역에서 N번역까지 도달하는 최단경로를 찾아주면 된다. 간선에는 가중치도 없기 때문에 그냥 보기에는 상당히 간단해 보였다. 하지만 금방 하이퍼튜브라는 컨셉을 정확히 이해하지 못했음을 깨달았다. 주어지는 경로상 존재하는 역들을 모두 각각 연결하고 하이퍼튜브로 연결된 경로에 대한 비용은 1로 계산 하는 형태로 이해하고 풀었었는데 메모리 제한에 걸리는 상황이 발생했다. 문제의 설명도 너무 짧아 더욱 이해하기 어려웠다. 문제의 포인트 하이퍼튜브 컨셉 이..