9938. 방 청소

요즘 플레 공부하는 중. 나름 3시간정도 고민해 봤지만, 플레3을 내 실력으로 풀 수 없으므로(......) 답 보고 공부한 내용을 올린다.

9938번: 방 청소

---

어린이날을 맞아 바닥에 어질러진 술병을 서랍에 넣으려 한다. 각 술병은 서랍 두 곳 중 하나에 들어갈 수 있다. 문제에서 주어진 규칙대로 술병을 넣을 때, 각 술병을 넣을 수 있는지 구하는 문제이다.

 

엥 이거 완전 이분 매칭 아니냐?

아니다

정점이 더 많은 집합의 정점이 $V$개이고 간선이 $E$개인 이분 매칭의 시간 복잡도는 $O(VE)$이다. 이 문제에서는 정점이 최대 30만 개이고 간선은 최대 60만 개이므로 무조건 시간 초과이다.

까먹었지 뭐야

그럼 어떻게 풀어야 하는가

놀랍게도 union find를 사용하면 풀 수 있다.

????????????

서랍에 대한 union find를 정의하자. 각 서랍의 root는 이 서랍에 들어있는 술이 들어갈 수 있는 다른 서랍이다.

 

정의에 의해 ``find(a)``는 ``a``에 들어있던 술을 옮길 때 맨 마지막으로 움직이는 술병이 들어가는 위치를 의미한다. 술병을 재귀적으로 움직이기 때문에 마지막으로 움직이는 술병은 ``a``가 아닐 수도 있다. 어쨌든 계산된 서랍이 비어 있다면 ``a``에 들어있는 술병을 옮길 수 있다.

 

구현은 똑같지만 전혀 새로운 의미를 담을 수 있다. Union find를 이렇게 쓸 수도 있구나.

 

merge는 이 서랍에 들어있는 술병이 들어갈 수 있는 다른 위치를 저장해야 한다. 그냥 b를 a에 연결하면 된다.

void merge(int a, int b) // a에 들어있는 술은 b에도 들어갈 수 있음
{
    int root1 = find(a), root2 = find(b); // 경로압축
    if (root1 == root2)
        return;
    root[root1] = root2;
}

 

이제 문제의 1~4번 조건을 순서대로 구현하면 된다. 참 신기하죠?

Union find가 가능한 이유

서랍 ``a``에 들어있는 술병을 옮겨야 한다고 가정하자. 이 술병은 ``b``에도 들어갈 수 있다. 그런데 ``b``에도 술병이 들어있다면, 먼저 ``b``의 술병을 옮겨야 한다. ``b``에 들어있는 술병은 ``c``에도 들어갈 수 있다. 그런데 ``c``에도 술병이 들어있다면....

 

위처럼 술병을 옮기는 위치를 재귀적으로 계산하게 되는데, 이 과정을 연결+압축하기 위해 union find를 사용할 수 있다. 술병이 들어갈 수 있는 다른 위치가 하나뿐이라 root를 정의할 수도 있고. 술병이 들어갈 수 있는 서랍이 3개 이상이었다면 union find를 쓸 수 없다. 이러면 진짜 이분 매칭밖에 답이 없지 않나.

---

오늘도 하나 배워간다. 사실 union find에서 값을 갱신하는 문제를 풀고 싶었는데, 뜻하지 않은 가르침을 얻게 됐다.