9938번
-
백준 9938번 방 청소 :: 마이구미알고리즘 풀이/디스조인트-셋 2017. 11. 9. 20:55
이 글은 백준 알고리즘 문제 9938번 "방 청소" 를 풀이한다.풀이 방법으로는 디스조인트-셋 자료구조를 이용한다.개인적으로 보면, 굉장히 어려운 문제가 된다.문제 링크 - https://www.acmicpc.net/problem/9938디스조인트 셋 이해 - http://mygumi.tistory.com/246 은기는 술병 N개(1부터 N까지 번호가 매겨져 있다)와 서랍 L개(1부터 L까지 번호가 매겨져 있다)를 가지고 있다. 술병은 은기의 방 바닥에 흩어져 있고, 어린이날을 맞이해 방 청소를 하려고 한다. 서랍에는 술병이 하나 들어갈 수 있다. 나중에 원하는 술을 빠르게 찾을 수 있게 하기 위해 은기는 각각의 술병이 들어갈 수 있는 서랍의 번호 Ai와 Bi를 공책에 적어 놓았다.은기는 술병을 1번부터..