[KOI 초등부] BOJ 17616 등수 찾기 (2019 2차 대회)

이 풀이는 homebody님의 풀이를 보고 이해하며 작성한 것입니다.

처음에는 줄세우기 문제와 비슷하다고 생각했는데, 누가 더 잘 하고, 못하고에 맞춰서 정렬하는 건 쉽지만 그 범위를 알아내는 건 어려웠다.

위상 정렬로 풀 땐, 2번 정점의 최대, 최소 등수를 구하기가 매우 어렵다

 

그래서 반대로 root 노드로부터 떨어진 거리를 각각 기록하고, 각 정점의 자식 수를 기록해서 같은 거리에 있는 그래프들의 순위 변화에 따라서 어떻게 등수가 바뀌는지 계산하려고 했지만 구현이 까다로울 뿐더러 연결 그래프가 2개 이상인 경우에는 답도 구할 수 없어서 결국 풀이를 봤다. 

 

아이디어는 간단한데, 그래프를 두 개로 분리해서 "나보다 등수가 높은 그래프"와 "나보다 등수가 낮은 그래프"로 관리하는 것이다. (이걸 어떻게 생각했을까...) 예를 들어서 경민이가 형곤이보다 등수가 높다고 해보자.

 

그림을 "나 보다 못 하는 그래프"에서는 경민이가 형곤이보다 잘하기 때문에, 경민이가 형곤이를 가리킨다. 반대로 "나 보다 잘 하는 그래프"에서는 형곤이가 경민이를 가리킨다. 아직은 두 명이라 문제가 쉽긴 한데, 학생을 늘릴 수록 이 모델링의 간결함이 드러난다. 이제 영석, 승민이라는 학생이 경민이보다 등수가 높다고 해보자.

 

승민이는 최대로 몇 등, 최소로 몇 등일까? 이 문제는 쉽게 해결되는데, 여기서 확실한 사실이 두 가지 있다.

1. 어떤 상황이든 승민이는 "나보다 못 하는 그래프에서 승민이와 연결된 친구들"보다는 등수가 높다.

2. 어떤 상황이든 승민이는 "나보다 잘 하는 그래프에서 승민이와 연결된 친구들"보다는 등수가 낮다.

*나보다 잘 하는 그래프던, 못 하는 그래프던 간에 승민이와 영석이는 연결되어있지 않으므로 고려하지 않는다.

 

1, 2번을 통해서 승민이의 등수는 최소 3등, 최대 1등이라고 할 수 있다. (등수는 높아야 좋은 것이므로 그냥 최대, 최소로 표현하겠다.)

 

구현