Baekjoon 1956 운동 JAVa

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

1956번: 운동

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%201956

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 마을과 도로가 주어졌을 때 거리가 가장 짧은 사이클을 구하는 문제다.

 

해당 문제는 플로이드 와샬 알고리즘을 이용하였다. 

먼저 마을 최대수가 400이고 최대 거리가 10000이라서 MAX값을 4000000으로 두었고,

이후 입력 처리를 하기 전에 플로이드 와샬 알고리즘을 위해 자기 자신으로 가능 경우를 제외하고는

map를 MAX값으로 초기화하고 이후 도로의 정보를 map에 추가한다 (양방향 아님)

 

 이후 플로이드 와샬 알고리즘을 이용하여 최단거리로 갱신하고,

map를 탐색하는데 이때 i==j(자기 자신), i, j 혹은 j, i가 MAX값이면 사이클 생성에 실패하는 경우라 넘겨주고

이후 값들에 대해서는 플로이드로 갱신되어 있으니 map의 i, j와 j, i둘의 합을 구하면 사이클의 거리 값을 알 수 있고

이 값을 ans변수에 최솟값으로 갱신한다.

 

이후 ans값이 초기값과 동일하면 사이클이 없으므로 -1을 아닌 경우 원래의 값을 저장하고

최종적으로 출력해주어 문제를 해결했다.