[백준] 9938 - 방청소

www.acmicpc.net/problem/9938

9938번: 방 청소

학교에서 분리집합 스터디 이후 연습문제로 풀게된 문제이다.

난이도는 solved.ac 기준 플레티넘3 이다.

분리집합이라는 아이디어를 갖고 시작할 수 있다면 난이도는 골드 수준으로 내려갔을 것 같다.

 

문제 설명을 읽어보면 복잡하다.

술을 서랍에 정리하는 순서가 다음처럼 나와있다.

 

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

겉보기에는 복잡해보인다.

하지만 분리집합이라는 자료구조를 사용하면 이 문제는 그냥 분리집합 구현문제가 되어버린다.

아이디어는 간단하다.

저 1, 2, 3, 4 라는 과정의 순서를 생각하지 않고, 읽어보면 다음과 같은 것을 의미한다.

 

i 번째 술이 들어갈 수 있는 서랍 Ai 와 Bi 에 대해서

서랍 Ai가 속한 집합과 서랍 Bi가 속한 집합에 술병을 넣을 수 있다면 넣는다.

 

그냥 퉁쳐서 하나의 집합처럼 생각해도 되는 이유는,

서랍과 서랍이 술을 매개로 연결되어있다고 생각하면

해당 집합에 빈 공간이 있을 경우 3번, 4번 과정을 통해서 연쇄적으로 술을 이동시킬 수 있기 때문에

빈 공간에 술을 집어넣는 것이 반드시 가능하기 때문이다.

 

따라서 이 문제는 Ai, Bi를 입력받은 후,

Ai, Bi를 하나의 집합으로 합치고 (merge / union)

해당 집합에 최대 사이즈와 현재 사이즈를 재서 (find & size check)

술병이 들어갈 수 있으면 사이즈를 늘리고 LADICA를 출력한다.

만약 해당 집합의 최대 사이즈와 현재 사이즈가 같다면

SMECE를 출력하고 넘어간다.

 

정답 코드는 다음과 같다.

# 9938 방청소
import sys
def find(a):
    if a == disjointSet[a]:
        return a

    disjointSet[a] = find(disjointSet[a])
    return disjointSet[a]

def merge(a, b):
    a = find(a)
    b = find(b)
    if a == b:
        return
    if maxSize[a] < maxSize[b]:
        a, b = b, a
    disjointSet[b] = a
    maxSize[a] += maxSize[b]
    nowSize[a] += nowSize[b]
    maxSize[b] = 0
    nowSize[b] = 0

input = sys.stdin.readline
n, m = map(int, input().split())
disjointSet = [i for i in range(m+1)]  # i번째 요소의 루트(속한 집합의 루트)는 [i]
maxSize = [1 for i in range(m+1)]
nowSize = [0 for i in range(m+1)]
for i in range(n):
    a, b = map(int, input().split())
    merge(a, b)
    if nowSize[find(a)] < maxSize[find(a)]:
        nowSize[find(a)] += 1
        print("LADICA")
    else:
        print("SMECE")

#print(disjointSet)