백준 9938번 방청소

문제

은기는 술병 N개(1부터 N까지 번호가 매겨져 있다)와 서랍 L개(1부터 L까지 번호가 매겨져 있다)를 가지고 있다. 술병은 은기의 방 바닥에 흩어져 있고, 어린이날을 맞이해 방 청소를 하려고 한다.  서랍에는 술병이 하나 들어갈 수 있다. 나중에 원하는 술을 빠르게 찾을 수 있게 하기 위해 은기는 각각의 술병이 들어갈 수 있는 서랍의 번호 Ai와 Bi를 공책에 적어 놓았다.

은기는 술병을 1번부터 N번까지 순서대로 정리할 것이고, 각각의 술병에 대해서 다음과 같은 과정을 거친다.

1. 서랍 Ai가 비어있다면, i번 술을 그 서랍에 보관한다.
2. 서랍 Bi가 비어있다면, i번 술을 그 서랍에 보관한다.
3. Ai에 들어있는 술을 다른 서랍으로 이동시킨다.(다른 서랍은 Ai에 들어있는 술이 들어갈 수 있는 서랍 중 하나이다) 만약, 그 서랍에도 이미 술이 들어있다면, 그 술을 다른 서랍으로 이동시킨다. 이런 과정을 거쳐서 빈 서랍을 하나 찾아 술을 모두 이동할 수 있는 경우에는, 술을 이동시키고 i번 술을 Ai에 보관한다. 불가능한 경우에는 다음 규칙으로 넘어간다.
4. Bi에 들어있는 술을 다른 서랍으로 이동시킨다. 만약, 그 서랍에도 이미 술이 들어있다면, 그 술을 다른 서랍으로 이동시킨다. 이런 과정을 거쳐서 빈 서랍을 하나 찾아 술을 모두 이동할 수 있는 경우에는, 술을 이동시키고 i번 술을 Bi에 보관한다. 불가능한 경우에는 다음 규칙으로 넘어간다.
5. 위의 과정이 모두 불가능한 경우에는 i번 술을 그 자리에서 마셔버린다. (은기는 전혀 취하지 않는다)

각각의 술에 대해서, 서랍에 보관할 수 있는지, 그 자리에서 마셔버리는지를 구하는 프로그램을 작성하시오.

문제풀이

사용한 알고리즘 : Union-Find

(1) 생각

 서랍 2개가 입력으로 들어오면 이 서랍 두 개를 하나의 component로 union 해줍니다.
 만약 1 3 , 2 3 으로 입력이 주어지면 1 2 3 이 하나의 component 겠지요.
 각 component 가 수용 가능한 술병의 수와 사용중인 서랍의 술을 각각 저장하여 수용 가능성을 판단할 것입니다.

(2) 코드 5~9

 ' R[x] : 기본적인 Union-Find를 위한 root 저장. 각각 -1로 초기화 '
 ' howmany[x] : x를 root 로 하는 component가 저장하고 있는 술의 수 '
 로 설정하였습니다.

(3) 코드 11~25

 Find 는 기본적인 Union-Find 입니다.
 Union 의 경우, aRoot 의 component와 bRoot의 component를 합쳐줄 때,
 R[aRoot] += R[bRoot] 로 수용 가능한 술의 수를 저장해주었습니다.
 즉, aRoot 의 수용 가능한 술의 수 = - R[aRoot] 가 됩니다.
 이후 갖고 있는 술병의 수도 합쳐줍니다.

(4) 코드 31~44

 x y 가 입력 될 경우, 일단 둘을 union 해줍니다.
 이후 해당 component 가 수용 가능한 술의 수가 갖고있는 술의 수보다 큰지 여부에 따라 답을 정해주면 됩니다.