어흥
[백준 9938] 방 청소 (C++) 본문
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/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;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 1786] 찾기 (JAVA) (0) | 2020.04.10 |
---|---|
[백준 16916] 부분 문자열 (JAVA) (0) | 2020.04.10 |
[백준 10775] 공항 (C++) (0) | 2020.04.10 |
[백준 1976] 여행 가자 (C++) (0) | 2020.04.09 |
[백준 1197] 최소 스패닝 트리 (Prim, Kruskal) (JAVA) (0) | 2020.04.09 |
Comments