3665. 최종 순위

몇 달 동안 프로젝트와 과제에 치여 살다가, 시험기간을 맞아 오랜만에 백준 문제를 풀었다. 분명 시험기간인데 평소보다 더 여유로운 건 뭐지..? 이것이 오픈북 효과인가?

 

3665번: 최종 순위

---

작년 순위와, 올해 순위가 바뀐 팀의 쌍이 주어진다. 이때 올해 순위를 결정할 수 있을까?

 

순위라는 말에서 위상 정렬을 생각해 내야 한다. 기존에 주어진 순위에서 두 팀간의 순위 관계를 알 수 있고, 올해 변경된 순위 관계를 반영하여 위상 정렬을 하면 된다.

 

위상 정렬을 하기 위해 먼저 그래프를 만들어야 한다. 연결 방향을 두 가지로 정할 수 있는데, 하나는 높은 순위에서 낮은 순위로 연결하는 방법이고, 다른 하나는 반대로 연결하는 경우이다. 위상 정렬에서 '진입 차수'를 중요하게 사용하기 때문에, 높은 순위에서 낮은 순위로 연결하여 그래프를 만들었다. 이때 순위가 인접한 두 팀만 연결하면 안 된다. 모든 팀끼리 연결 관계가 있어야 한다.

 

그 다음 올해 바뀐 순위를 그래프에 반영하면 된다. (a, b)가 주어질 때, 그래프에서 a->b 또는 b->a 중 하나만이 존재한다. 기존에 존재했던 관계를 지우고 다른 하나로 대체하면 된다. 

 

이제 위상 정렬을 수행하면 된다.

# IMPOSSIBLE과 ? (펼치기)

모순된 정보가 주어질 때도 있다. 이건 위상 정렬이 불가능한 경우와 같다.

 

반면 '확실한 순위를 정할 수 없는 경우'는 없는 듯 하다. 정확히 증명하지는 않았지만, 이미 작년 순위가 주어져 있고 올해에는 그 순위를 수정하는 것이기 때문이라 추측한다. 

---

위상 정렬을 거꾸로 적용하는 문제였다. 그래도 이 정도면 할 만하지..

 

시험 끝나면 문제 많이 풀어야지.