이동식 저장소

어제 union find 공부한 게 기억에 남아서, 대충 비슷해 보이는 문제를 풀기로 했다.

두 학생의 상대적인 순위를 비교한 데이터가 주어질 때, 학생 $x$의 순위가 될 수 있는 최고/최저 순위를 구하는 문제이다.

어제 공부한 union find 업데이트를 적용해 보자. 등수가 가장 높은 학생을 루트로 하는 집합이 있을 때, $x$보다 순위가 높은 학생을 $above[x]$라고 정의하자. $above[x]$는 대략 이렇게 구할 수 있을 듯하다.

int find(int n)
{
    if (root[n] == n)
        return n;
    auto parent = find(n);
    above[n] += above[parent] + 1;
    return root[n] = parent;
}

merge는 어떻게 짜지? 어제 문제에서 모든 간선의 길이가 1인 그래프라고 생각하면 되지 않을까?

void merge(int a, int b, int w)
{
    int root1 = find(a), root2 = find(b);
    if (root1 == root2)
        return;
    // merge?
    above[root2] = above[a] + 1 - above[b];
    root[root2] = root1;
}

흠.. 그런데 이렇게 하면 $above[x]$의 정의에 맞지 않는다. $above$는 나보다 무조건 순위가 높은 학생의 수인데, 위의 merge 함수는 $a$와 $b$가 속한 집합의 크기 차이를 구하고 있지 않는가?

생각해 보니, 어제 문제와는 아주 큰 차이가 있다. 어제 문제에서는 무게의 차이까지 모두 주어졌기 때문에 무게 차이를 merge할 수 있었지만, 이 문제에서 주어지는 a b 쌍은 a가 b보다 정확히 몇 등이나 높은지 알려주지 않는다. 

오히려 union find보다 위상 정렬을 써야 하지 않을까.

위상 정렬?

잘 생각해 보면, $x$의 최고 순위는 ($x$보다 등수가 확실히 높은 학생의 수) + 1이고, $x$의 최저 순위는 $N$ - ($x$보다 등수가 무조건 낮은 학생의 수)이다. 

그런데 위상 정렬은 한 방향으로밖에 정렬하지 못한다. 따라서 $x$보다 등수가 확실히 높은 학생과 확실히 낮은 학생을 구하기 위해 위상 정렬을 최소 2번 실행해야 한다.

그럴거면 그냥 bfs 2번 하는 게 쉽지 않냐?

맞다

높은 순위에서 낮은 순위로 가는 간선과 낮은 순위에서 높은 순위로 가는 간선 두 개를 만들고, 각각 bfs하면 된다. 참 쉽죠? union find 없이도 풀 수 있다~

에잉.. union find는 따로 연습해야지..