문제 이해 단계 https://www.acmicpc.net/problem/1238 N개의 마을에 연결된 M개의 단방향 도로가 존재한다. 각 도로에는 오고 가는 시간(비용)이 존재한다. N개의 마을 중 특정 마을 X로 왕복해야 하는데, 어느 마을에서 출발하는 것이 가장 시간이 오래 걸리는가? 그때의 소요 시간을 구하는 출력하는 문제 문제 접근 단계 문제 유형 유추 N개의 마을에 연결된 M개의 단방향 도로라는 말을 읽자마자 바로 그래프 탐색이 떠올랐다. 마을을 정점으로 치환하고, 단방향 도로를 단방향 간선으로 본다. 그리고 걸리는 시간을 각 간선의 가중치로 보면 완벽한 그래프 탐색 문제이다. 로직 어쨌든 이 학생들은 무조건 최단 거리로 오고 간다고 했다. 그래프 탐색에서 최단거리라고 하면 생각나는 것이 크루..