최단 경로. [1956]

[1. 문제 설명]

임의의 방향 그래프 내 Cycle 경로 중 길이가 가장 짧은 것을 출력하도록 한다.

없을 경우 -1 을 출력

 

 

 

[2. 풀이 접근]

A. Cycle

=> 그래프에서 Cycle 은 시작점에서 출발하여 다시 자기자신으로 돌아오는 것을 말한다.

 

문제에서 지정한 출발지점이 없으니, 모든 시작정점에서 사이클이 있는지 없는지 판별하고,

있다면 그 중 최소 경로를 반환해야 하는데,

 

사이클을 찾는 것은 둘째치고, 각 시작정점에서 최단 경로를 찾는 것만으로도 시간초과가 발생할 수 있다.

(관련 예제=> https://testkernelv2.tistory.com/348)

 

문제 입력에서 정점의 개수가 400 개이므로 플로이드-와샬 알고리즘 사용을 고려해볼 수 있다.

플로이드-와샬 알고리즘 사용 시 사이클을 판단 하는 조건은 아래와 같다.

 

from -> middle -> to 에서

from == to && from != middle

아래 그림과 같은 형상이다.

 

 

[3. 코드]