백준 2458번 키 순서

< 백준 2458번 키 순서 - 마포 코딩박 >

사용한 알고리즘: 플로이드 와샬


 학생들의 키 결과가 입력으로 주어졌을 때, 자신의 키가 몇번째인지 아는 학생 수를 구하는 문제였습니다.
 자신을 제외한 모든 학생에 대해, 자신에서 학생으로 갈 수 있거나, 학생에서 자신으로 올 수 있으면 자신이 몇번째인지 알 수 있습니다.
 따라서 플로이드 와샬을 통해 각 학생들간의 거리를 구하고, 자신을 제외한 모든 학생에 대한 거리가 있는 경우를 찾았습니다.

풀이는 다음과 같습니다.

(1) 모든 학생들 간의 거리는 초기값을 Infimum으로 설정해 둡니다. ( 플로이드 와샬을 구현하기 위해 )

(2) 입력으로 주어지는 학생 a,b 사이의 거리를 저장합니다. ( 거리를 1 로 생각했습니다. )

(3) 플로이드 와샬 (for 구문 3번) 을 통해 모든 학생들 사이에 존재하는 거리를 구합니다.

(4) 각 학생들이 아는 키의 경로 (거리가 Infimum 보다 작은 경우) 를 구할겁니다.

(5) 학생 i - > j 의 거리가 Infimum 보다 작은 경우 ( 경로가 존재하는 경우 ) i 가 아는 학생수 ++ , j 가 아는 학생수 ++ 을 해줍니다.

(6) 학생수가 N-1 (자신을 제외한 전체) 인 학생인 경우가 구하고자하는 학생(수) 입니다.

처음 말씀드린 생각 ( 모든 경로를 아는 학생이 답이다 ) 를 생각하고,
플로이드 와샬을 구현하는 문제였습니다. 해보지는 않았지만, 다익스트라나 벨만 포드를 써도 상관 없을 것 같습니다.