[BOJ]2458번: 키 순서

문제: https://www.acmicpc.net/problem/2458

---

모든 학생들 간의 관계 (모든 노드간의 순서쌍)을 구하는 문제이므로 플로이드로 해결할 수 있는 문제입니다.

N 제한이 작아 N^3을 돌려도 해결할 수 있다는 점을 단서로 삼을 수 있습니다.

 

학생들간의 키 관계를 담은 3차원 배열 int[][][] dist를 선언하였고 정보를 담아줍니다.

dist[0][a][b] = 1이 의미하는 바는 a가 b보다 작은 경우입니다.

dist[1][a][b] = 1이 의미하는 바는 a가 b보다 큰 경우입니다.

 

그래서 플로이드쌍을 전부 갱신해준 뒤 dist[0][][], dist[1][][]를 순회해서 비교 횟수가 N-1인 학생인 자신의 키 순서를 알 수 있습니다.

---

코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ2458.java