최단경로. [2458]

[1. 문제 설명]

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

---

[2. 풀이 접근]

두 학생의 키를 비교한 결과들을 그래프로 모델링한다.

• 노드: 학생 번호
• 간선: 두 학생 간 비교 결과
  => 작은 학생에서 큰 학생으로 연결

그래프로 모델링하고 나면, 

문제에서 요구하는 부분 문제 (어떤 학생이 자신의 키가 몇 번째인지 알 수 있는가?) 를

아래 질문으로 답할 수 있다.

• 어떤 노드에서 다른 모든 노드로 가는 경로가 존재하는가?
• 어떤 노드에서 다른 모든 노드와 그 관계가 형성되는가?
  => 직접 연결 혹은 간접적으로 연결

여기서 좀 헷갈렸던 부분은 삭선한 부분이다.

왜 다른 모든 노드로 가는 경로로 체크하면 안되냐는 것이다.

 

위 그림에서 4번만이 자신의 키가 몇번째 인지 알 수 있다.

4번은 3번으로 가는 경로가 없는데도 말이다.

 

그 이유는 4번은 3번으로 갈 순 없지만, 3번에서 4번으로는 갈 수 있기 때문이다.

4번 입장에서 보면 3번이 자신으로 들어오는 노드로 볼 수 있고,

4번과 3번은 그 관계를 알 수 있게 되기 때문이다.

 

그래서 4번이 자신의 키가 몇번째 인지 알 수 있는 학생인 것을 판별할 때,

4->3 이 연결되었는지 확인하는 것과 더불어,

3->4 로 연결되는지 확인하는 작업이 필요하다.

 

이제 해야 할 것은 모든 출발지-도착지 노드 간 그 경로가 있음을 알면 된다.

이 작업은 플로이드-워셜 알고리즘을 통해 구할 수 있다.

 

시간 복잡도가 O(N³) 이고,

N 은 최대 500이어서, 대강 1.25*10⁸ 번 으로 계산되어,

1억을 살짝 넘지만, 

플로이드-워셜 알고리즘은 반복문 내부가 상당히 심플해서

시간 내에 동작한다.

---

[3. 코드]