Jonyo Programming

[BOJ 1613(G3)리뷰] 플로이드-와셜을 이용한 알고리즘이다. 보통 모든 노드간의 최단거리를 구하는데 사용되지만 이러한 문제에도 응용할 수 있다. 결국 각각의 노드는 모든 노드에 대해 자신과 연결된 노드를 이용하여 노드간의 관계를 정의할 수 있냐 없냐로 나뉜다. 그리하여, 플로이드-와셜 알고리즘을 통하여 모든 연결을 확인하여 연결이 가능한 경우에만 배열에 기록하면 된다. 예를들어, "1 2"라는 입력은 1번사건이 2번사건보다 먼저 일어났다는 의미이다. 이후에 "2 3"이라는 입력이 있다면 1->2->3의 관계를 통해 1번사건이 3번사건보다 먼저 일어났다는것을 알 수 있다. 이렇게 알고리즘을 적용하고나면 연결여부를 기록한 배열에는 각각의 노드마다 자신보다 뒤에 일어난 사건의 번호들의 index를 가지..