이 문제는 얼핏 보기에는 까다로운 문제처럼 보이지만, 문제의 상황을 그래프로 표현하여 풀면 보다 간단해진다.N개의 물건들을 각각 노드로 표현하고, 각 물건 무게 사이의 관계 를 아래와 같은 규칙을 통해 단방향 간선으로 표현하자.
[x] > [y]와 같은 입력이 주어졌을 때, 이것을 x번 노드에서 y번 노드로 가는 단방향 간선 으로 표현한다.
즉, 그래프에는 N 개의 노드와 M 개의 단방향 간선이 있다.
이 그래프에서 두 물건 사이의 무게 관계를 쉽게 알 수 있는데, 두 물건 p,q 의 무게 관계 를 알 수 있는 경우는 p번 노드에서 q번 노드로 가는 경로가 있거나, q번 노드에서 p번 노 드로 가는 경로가 있는 경우다.
위에서 설명한 것과 같이 그래프를 만들고, DFS, BFS나 Floyd-Warshall 알고리즘을 사용하여 O(N^3) 시간복잡도에 해결할 수 있다.