백준 2458: 키 순서 (Swift)

Floyd-Warshall 알고리즘을 이용해 풀이하였다.

우리가 알고있는 Floyd-Warshall알고리즘은, 모든 node에서 모든 node까지의 최단거리를 구할 수 있는 알고리즘이다.

 

Floyd-Warshall

보통 2차원 배열 (n x n)을 INF로 채워넣은 후, 우리가 알고있는 거리를 배열에 갱신해 넣고,

3중 for문을 돌려 모든 node -> 모든 node 최단거리를 얻어낸다

 

이 문제에서는,

거리는 우리의 관심 밖이고, a번 node에서 b 번 node로 길이 있는지, b부터 a까지 길이 있는지 여부이다.

따라서 2차원 배열을 0으로 채워넣고, 길이 있는 경우 1로 갱신하도록 알고리즘을 작성하였다.

 

이렇게 하면 마자막 30번 줄~   내 앞, 뒤에 몇명이 있는지 셀 때 훨~~ 씬 수월해진다.

기존의 플로이드-워셜 알고리즘과 같이 INF로 채워넣고 수행했다면, 일단 INF인지 아닌지 비교하는 과정이 추가되었을 것이고, 코드로도 덜 직관적이었을 것이다.

 

길이 있으면 1, 없으면 0 이므로, 그냥 다~ 더한 후 합이 n-1이면 내 순서를 아는 것이라고 판단하면 된다!