문제 출처 : https://www.acmicpc.net/problem/10159
무게가 서로 다른 N 개의 물건이 있다. 각 물건은 1부터 N 까지 번호가 매겨져 있다.
예를 들어, 총 6개의 물건이 있고, 다음 5개의 비교 결과가 주어졌다고 가정하자. ([1]은 1번 물건의 무게를 의미한다.)
[1]>[2], [2]>[3], [3]>[4], [5]>[4], [6]>[5]
우리는 [2]>[3], [3]>[4]로부터 [2]>[4]라는 것을 알 수 있다. 하지만, 물건 2와 물건 6을 비교하는 경우, 앞서의 결과만으로는 어느 것이 무거운지 알 수 없다. 이와 같이, 물건 2는 물건 1, 3, 4와의 비교 결과는 알 수 있지만, 물건 5, 6과의 비교 결과는 알 수 없다. 물건 4는 모든 다른 물건과의 비교 결과를 알 수 있다.
문제만 보고 그래프를 떠올리기가 쉽지 않은 문제였다. 물론 그래프를 떠올렸다고 해도 어떻게 접근을 해야할지 생각을 좀 해봐야했다.
정점과 정점의 사이의 최단 거리를 구하는 플로이드 와샬 알고리즘을 떠올려야한다.
정확히는 거리를 구하는게 아니라 거리의 유무를 구해야한다. 입력 값은 대소값을 구하기 때문에 단방향이다. 그렇기에 임의의 정점1에서 어떤 정점2을 거쳐서 다른 정점3으로 못가는 경우가 발생할 수 있다.
1 → 2 ← 3 같은 경우는 1에서 2를 거쳐 3으로 가지 못하니 연결되어 있지 않다고 할 수 있다.
플로이드 와샬은 INF로 이어져있지 않은 정점을 표시하기 때문에 유무를 구할 수 있다.
플로이드 와샬 알고리즘으로 각 정점 사이의 거리를 구하는데 최단거리를 구하는게 아니기 때문에 연결 되어있다면 1, 연결되어있지 않다면 0을 넣어주면 된다.
그래프에서 각 정점과 다른 정점 사이의 간선이 단방향으로 있으니 초기화를 한 방향만 처리해준다.
그리고 플로이드 와샬을 하면 이어지면 1이 들어가 있고 아니면 0이 들어가 있으니 두 정점이 0인 경우는 이어지지 않았다는 의미이므로 그 때 답을 구하면 된다.