백준 9938: 방 청소

문제 요약

은기는 술병 N개(1부터 N까지 번호가 매겨져 있다)와 서랍 L개(1부터 L까지 번호가 매겨져 있다)를 가지고 있다. 술병은 은기의 방 바닥에 흩어져 있고, 어린이날을 맞이해 방 청소를 하려고 한다. 서랍에는 술병이 하나 들어갈 수 있다. 나중에 원하는 술을 빠르게 찾을 수 있게 하기 위해 은기는 각각의 술병이 들어갈 수 있는 서랍의 번호 Ai와 Bi를 공책에 적어 놓았다.

은기는 술병을 1번부터 N번까지 순서대로 정리할 것이고, 각각의 술병에 대해서 5가지 과정을 거친다.

각각의 술에 대해서, 서랍에 보관할 수 있는지, 그 자리에서 마셔버리는지를 구하는 프로그램을 작성하시오.

문제 분류

• 자료 구조
• 분리 집합

문제 풀이

각 서랍을 연결지어 집합으로 생각하는 유니온 파인드 문제이다. 각 조건을 살펴보자. 각 술마다 a 혹은 b의 서랍으로 넣어야 한다. 각 조건을 차례로 확인하는데, a가 빌 경우 a에 넣고, 그렇지 않으면 b를 살펴서 b가 비면 b서랍에 넣는다. 여기서 두 서랍이 모두 비었을 경우, a에 이미 들어간 술을 다른 가능한 곳으로 옮기고 그 a에 술을 넣는다. 이것도 안되면 b의 술을 똑같이 옮기고, 해당 위치에 술을 넣는다. 모두 불가능하면 마신다.

여기서 각 서랍을 집합으로 파악한다. 가령 어떠한 술이 a에서 b서랍으로 옮겨갈 수 있으면 a의 루트는 b가 되는 것이다. 그렇게 했을 때, 나중에 다른 술이 a의 자리에 넣으려고 하면, 이미 a에는 술이 있으므로 a가 아닌 find(a)의 자리에 술을 넣는 것이 3번 조건과 상통한다. 4번도 마찬가지로 b의 위치에 술이 이미 있으면 find(b)로 가능한 위치를 찾는다. 여기서 살펴볼 것은 각 노드마다 술이 비어있는가를 파악해야 한다는 것이다. 나는 m[]으로써 각 서랍별 보관되는 술의 번호를 부착해주었다. 해당 값이 0일때는 비어있다는 뜻이 된다. 즉, 어떠한 집합의 루트를 제외한 노드들은 모두 술이 이미 보관되어있는 상태이고, 루트에서만 술이 보관 가능한지의 여부를 따지면 된다.

입력을 받아 각 차례로 조건을 따져주었고, a에 보관될 경우 b를 루트로, b에 보관될 경우 a를 루트로 설정하여 집합을 만들었다. 조건을 차례대로 따져야 하므로 a와 b가 모두 안될 경우에만 find(a)로 a의 술을 옮기는 경우를 보았고, 그래도 안되면 find(b)로 b 서랍의 술을 옮기는 경우를 파악했다. 마지막으로 양 a와 b 집합의 루트가 모두 술이 보관되어 있을 경우 SMECE를 출력했다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

int p[300001], m[300001];

int find(int n) {
	if (p[n] == n) return n;
	p[n] = find(p[n]);
	return p[n];
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	p[b] = a;
	printf("LADICA\n");
}

int main()
{
	int n, l, in, in2;
	scanf("%d%d", &n, &l);
	for (int i = 0; i <= l; i++)
		p[i] = i;
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &in, &in2);
		if (m[in] == 0) {
			m[in] = i;
			merge(in2, in);
		}
		else if (m[in2] == 0) {
			m[in2] = i;
			merge(in, in2);
		}
		else if (m[find(in)] == 0) {
			m[find(in)] = i;
			merge(in2, in);
		}
		else if (m[find(in2)] == 0) {
			m[find(in2)] = i;
			merge(in, in2);
		}
		else
			printf("SMECE\n");
	}
}

후일담

처음에 집합을 구성할 때, 서랍이 N이 아닌, L개 있다는 것에 주의하여 집합을 생성해야 한다.