[백준 9938] 방 청소 (C++)

문제 링크: https://www.acmicpc.net/problem/9938

9938번: 방 청소

1. 주의할 점

- 한번 채워진 서랍은 항상 채워진 상태를 유지한다

- 서랍이 채워져 있는지 확인하는 배열이 필요하다

- A와 B서랍이 따로 존재하는 것이 아닌,  A위치의 서랍이 채워져 있다면 B위치의 서랍을 차선책으로 선택한다

 

2. 구현

- 각 서랍의 부모(Par[]배열)를 자기 자신으로 지정한다

- A위치의 서랍에 술을 넣을 수 있는 경우, A에 술을 넣고 A의 부모로 차선책인 B를 설정한다 (해당 공간에 I번째 술을 넣을 수 있다는 표시)

- 위의 과정이 불가능하며, B위치의 서랍에 술을 넣을 수 있는 경우, B에 술을 넣고 B의 부모로 A를 설정한다 (I번째 술을 넣을 수 있는 서랍은 A의 집합과와 B의 집합만 존재하기 때문)

- 위의 과정이 불가능하며, Find_par(A)의 함수를 통해 I번째 술을 넣을 수 있는 다른 공간이 있는지 확인한다 (A의 집합중에서 I번째 술을 넣을 수 있는 서랍이 있는지 확인)

- 위의 과정이 불가능하며, Find_par(B)의 함수를 통해 I번째 술을 넣을 수 있는 다른 공간이 있는지 확인한다 (B의 집합중에서 I번째 술을 넣을 수 있는 서랍이 있는지 확인)

- 위 4가지 중 1가지라도 가능하면 LADICA를, 모두 불가능하면 SMECE를 출력한다

 

#include <iostream>
using namespace std;
int par[300001];
bool visit[300001] = { false, };

int find_par(int x) {
	if (par[x] == x) return x;
	return par[x] = find_par(par[x]);
}

//a의 부모를 b로 두다
void make_union(int a, int b) {
	a = find_par(a);
	b = find_par(b);
	if (a != b)
		par[a] = b;
	cout << "LADICA\n";
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, l, a, b;
	cin >> n >> l;
	for (int i = 1; i <= l; i++)
		par[i] = i;

	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		if (!visit[a]) {		//a에 넣을 수 있는 경우
			visit[a] = true;
			make_union(a, b);
		}
		else if (!visit[b]) {		//a의 차선책인 b에 넣을 수 있는 경우
			visit[b] = true;
			make_union(b, a);			
		}
		else if (!visit[find_par(a)]) {		//3. a,b에 넣지 못해 빈 서랍을 찾는 경우
			int idx = find_par(a);
			visit[idx] = true;
			make_union(a, b);
		}
		else if (!visit[find_par(b)]) {		//4. a,b에 넣지 못해 빈 서랍을 찾는 경우
			int idx = find_par(b);
			visit[idx] = true;
			make_union(b, a);
		}
		else 
			cout << "SMECE\n";		
	}
	system("pause");
	return 0;
}