백준 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 가 수용 가능한 술의 수가 갖고있는 술의 수보다 큰지 여부에 따라 답을 정해주면 됩니다.

	#include <bits/stdc++.h>
	using namespace std;
	int N, L;
	// R[x] > 0 일때 : x는 component의 root가 아님. R[R[x]] 를 따라 root를 찾는다.
	// R[x] < 0 일때 : x의 component가 수용 가능한 술병의 개수
	int R[333333];
	// howmany[x] : x 서랍을 root로 한 component가 갖고 있는 술병 수
	int howmany[333333];
	int Find(int a) {
	if (R[a] < 0) return a;
	return R[a] = Find(R[a]);
	}
	void Union(int a, int b) {
	int aRoot = Find(a);
	int bRoot = Find(b);
	if (aRoot == bRoot) return;
	// component 합치기
	R[aRoot] += R[bRoot];
	R[bRoot] = aRoot;
	// 갖고 잇는 술 개수 합치기
	howmany[aRoot] += howmany[bRoot];
	howmany[bRoot] = 0;
	}
	int main() {ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	memset(R, -1, sizeof(R));
	cin >> N >> L;
	for (int i = 1; i <= N; ++i) {
	int x, y;
	cin >> x >> y;
	Union(x, y);
	int Root = Find(x);
	// R[Root] : -(Root 의 component가 수용 가능한 술병의 개수)
	// howmany[Root] : Root의 component가 이미 갖고있는 술병의 개수
	if (-R[Root] > howmany[Root]) {
	cout << "LADICA" << '\n';
	howmany[Root]++;
	}
	else
	cout << "SMECE" << '\n';
	}
	return 0;
	}

view raw BOJ 9938.cpp hosted with ❤ by GitHub