[백준/BOJ] 백준 9938번 : 방 청소

https://www.acmicpc.net/problem/9938

9938번: 방 청소

유니온 파인드를 활용해서 문제를 해결했다. vector<int> basket(300001, 0);에는 해당 서랍에 술이 들어 있는지 비어있는지를 나타냈다. 해당 술이 들어가고 난 뒤 해당 서랍에서 나중에 옮겨질 수 있는 서랍 쪽으로 유니온을 하고, 파인드를 통해 특정 서랍에 있는 술을 다른 서랍으로 옮길 수 있는지 확인하는 방법으로 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, l;
vector<int> parent(300001);
vector<int> basket(300001, 0);
vector<string> result;

void Pre()
{
	for (int i = 1; i <= 300000; i++)
		parent[i] = i;
}

int Find(int u)
{
	if (parent[u] == u)
		return u;

	return parent[u] = Find(parent[u]);
}

//u를 v쪽에 합친다
void Merge(int u, int v)
{
	u = Find(u);
	v = Find(v);

	parent[u] = v;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	Pre();

	cin >> n >> l;

	for (int i = 0; i < n; i++)
	{
		int a, b;
		cin >> a >> b;

		//서랍 a가 비어 있을때
		if (basket[a] == 0)
		{
			basket[a] = 1;
			Merge(a, b);

			result.push_back("LADICA");
		}

		//서랍 b가 비어 있을때
		else if (basket[b] == 0)
		{
			basket[b] = 1;
			Merge(b, a);

			result.push_back("LADICA");
		}

		//서랍 a에 들어있는 술을 다른 서랍으로 옮길 수 있을때
		else if (basket[Find(a)] == 0)
		{
			//최종적으로 옮겨지는 서랍 체크 (현재 술은 서랍 a에 들어가는것)
			basket[Find(a)] = 1;

			Merge(a, b);

			result.push_back("LADICA");
		}

		//서랍 b에 들어있는 술을 다른 서랍으로 옮길 수 있을때
		else if (basket[Find(b)] == 0)
		{
			//최종적으로 옮겨지는 서랍 체크 (현재 술은 서랍 b에 들어가는것)
			basket[Find(b)] = 1;

			Merge(b, a);

			result.push_back("LADICA");
		}

		else
		{
			result.push_back("SMECE");
		}
	}

	for (int i = 0; i < result.size(); i++)
		cout << result[i] << "\n";

	return 0;
}