BOJ 1613 역사

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

1613번: 역사

 

전후관계를 나타내기 위해 방향그래프를 이용했다.

• A 사건이 B사건에 우선하면 A->B라 표기

 

다시 문제로 돌아가면, 사건들의 전 후 관계가 주어졌을 때 다음과 같은 질의들이 주어진다.

•   A  C
•   C  B 

앞에 있는 사건이 우선해서 일어났으면 -1, 뒤에 있는 사건이 우선해서 일어났으면 1, 주어진 전후관계로 질의의 전후관계를 파악할 수 없으면 0을 출력한다.

 

문제 접근

전후관계와 관계 판단만을 보고 위상정렬을 이용한 문제라 생각하고 접근했지만, 위상정렬의 경우에는 정렬의 순서가 구현에 따라 여러가지 

 

 e.g

    A B C D

    A C B D

와 같이 나타날 수 있는데,

 

 

위의 경우 모두 위상정렬의 결과가 될 수 있어 B -> C인가? 라는 질의에 정확히 답하기 어렵다. (위상정렬을 1회 수행한 경우)

 

시간이 좀 걸리긴 했지만, 이 문제를 모든 정점에서 모든 정점의 최단거리 문제로 본다면, B -> C인가? 라는 질의가 주여졌을 때 B에서 C로의 최단거리가 존재하면 B에서 C 순서로 사건이 이루어졌다 볼 수 있다.

*문제에서 '물론 사건의 전후 관계가 모순인 경우는 없다.' 명시

 

플로이드 와샬을 이용하면 해결할 수 있는 문제였다.