[C++][백준] 용량 부족 - TRIE(5446)

문제

팀포2 덕후 연수는 팀포2를 다운받던 도중 하드 용량이 부족하다는 것을 알았다. 이때는 침착하게 팀포2를 하지 말거나 하드를 새로 사면 되지만 불가능했고, 결국 하드에서 쓸모없는 파일을 지워야만 한다.

연수는 또한 턱스 덕후여서 리눅스를 사용중이다. 리눅스에서 현재 디렉토리의 특정 파일을 지우려면 "rm 파일명"의 형식을 갖춰 명령하면 된다. 그러나 파일 개수가 너무 많을 경우 일일이 다 칠 수 없기에, 와일드카드 '*'를 사용할 수도 있다. "rm 문자열*" 형식으로 명령하면 현재 디렉토리에서 파일 이름이 "문자열"이거나 "문자열"로 시작하는 모든 파일이 한번에 삭제된다! 그러나 지워서는 안 되는 파일들 또한 존재한다. rm 명령어를 잘못 사용하여 이러한 파일들을 지우지 않도록 조심해야 할 것이다. 때에 따라서 "rm *"도 사용할 수 있긴 하다. 현재 디렉토리의 모든 파일을 지우고 싶을 때만...

모든 파일이 디렉토리 하나에 존재하고 연수가 그 디렉토리에 있을 때, 지우고 싶은 파일들을 모두 지우는 데 필요한 최소 rm 명령 횟수를 구하시오. 단, 사용할 수 있는 와일드카드는 '*' 뿐이며 반드시 제일 끝에만 사용해야 한다. 예를 들면 "rm *.txt"는 사용할 수 없다.

 

입력

입력은 여러 개의 테스트 케이스로 주어지며, 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 다음과 같은 형식이다.

• 첫째 줄에 지워야 하는 파일의 개수 N1이 주어진다. (1 ≤ N1 ≤ 1000)

• 이어서 N1개의 줄에 지워야 하는 파일명이 줄마다 하나씩 주어진다.

• 이어서 지우면 안 되는 파일의 개수 N2가 주어진다. (0 ≤ N2 ≤ 1000)

• 이어서 N2개의 줄에 지우면 안 되는 파일명이 줄마다 하나씩 주어진다.

파일 이름은 모두 1글자 이상 20글자 이하이며, 영문 대소문자, 숫자, 점(.)으로만 이루어져 있다. 하나의 테스트 케이스에 등장하는 모든 파일 이름은 서로 다르다.

 

출력

각 테스트 케이스마다 한 줄에 걸쳐 문제의 정답을 출력한다.

 

풀이

지워야 하는 파일, 지우면 안되는 파일 목록을 입력받고 몇번의 명령어를 통해 지워야 하는 파일들을 모두 지울 수 있는지 구하는 문제입니다.

 

이때 명령어는 두 종류로 구분할 수 있습니다.

명령어-1) 문자열*

: 문자열이거나 문자열로 시작하는 모든 파일을 삭제합니다.

 

명령어-2) 문자열 

: 문자열로된 파일을 삭제합니다.

 

먼저 트라이에 지워야 하는 파일, 지우면 안되는 파일 목록을 모두 삽입합니다.

그리고 트라이를 완전 탐색할 것입니다.(DFS)

 

BAPC는 지우면 안되는 파일입니다. 편의를 위해 지우면 안되는 파일은 빨간색상으로 표시하였습니다.

트라이에 지워야 하는 파일, 지우면 안되는 파일 목록을 모두 삽입후 완전 탐색을 진행한다고 했는데요,

먼저 빨강색(지우면 안되는 파일)의 경우 그 어떤 명령어도 내릴 수 없습니다. 지우면 안되기 때문입니다.

 

 

 

 

 

연이어 완전탐색을 진행하다가 .노드까지 왔습니다.

이때 지우면 안되는 노드가 없습니다. 

즉 우리에게는 이제 어떤 제약도 없습니다.

따라서 이 때 BAPC.* 명령어를 사용해서 하위 파일을 모두 삭제합니다.

이 경우 하위 노드를 모두 삭제 했기 때문에 아래로는 완전탐색하지 않아도 됩니다. 

즉 가지치기를 할 수 있습니다.

 

 

 

 

 

마찬가지로 problem.tex의 경우도 지워야하는 제약이 없기 때문에 p* 명령어를 사용해서 하위 파일을 모두 삭제합니다.

 

 

 

 

 

다른 케이스도 살펴보도록 하겠습니다.

완전 탐색을 계속 이어갑니다.

마찬가지로 빨강색(지우면 안되는 파일)의 경우 그 어떤 명령어도 내릴 수 없습니다. 지우면 안되기 때문입니다.

 

 

 

 

 

연이어 완전탐색을 진행하다가 t노드까지 왔습니다.

이때 지우면 안되는 노드가 없습니다. 

즉 우리에게는 이제 어떤 제약도 없습니다.

따라서 이 때 filt* 명령어를 사용해서 하위 파일을 모두 삭제합니다.

이 경우 하위 노드를 모두 삭제 했기 때문에 아래로는 완전탐색하지 않아도 됩니다. 

즉 가지치기를 할 수 있습니다.

 

 

 

 

 

완전 탐색을 계속 이어갑니다.

마찬가지로 빨강색(지우면 안되는 파일)의 경우 그 어떤 명령어도 내릴 수 없습니다. 지우면 안되기 때문입니다.

 

 

 

 

 

연이어 완전탐색을 진행하다가 n노드까지 왔습니다.

이때 지우면 안되는 노드가 없습니다. 

즉 우리에게는 이제 어떤 제약도 없습니다.

따라서 이 때 filen* 명령어를 사용해서 하위 파일을 모두 삭제합니다.

이 경우 하위 노드를 모두 삭제 했기 때문에 아래로는 완전탐색하지 않아도 됩니다. 

즉 가지치기를 할 수 있습니다.

 

 

 

 

 

 

다시 완전탐색을 진행할텐데 s노드는 방문할 필요도 없습니다.

왜냐면 지워야 하는 파일을 지우기 위한 명령어의 수를 세야 하는데

s 노드부터는 제거해야하는 파일이 없기 때문입니다.

제거해야하는 파일이 없는 노드는 살펴볼 이유가 없습니다.

이 경우에도 마찬가지로 가지치기를 해줄 수 있습니다.

 

 

 

 

 

마지막 케이스를 살펴보도록 합시다.

빨강색(지우면 안되는 파일)의 경우 지우면 안되기 때문에 그 어떤 명령어도 내릴 수 없다고했는데요,

우리는 clean 이라는 파일명을 가진 파일을 지워야만 합니다.

 

명령어에는 두가지 종류가 있다고 했는데요,

명령어-1) 문자열*

: 문자열이거나 문자열로 시작하는 모든 파일을 삭제합니다.

 

명령어-2) 문자열 

: 문자열로된 파일을 삭제합니다.

 

이 경우에는 명령어 2번 clean을 사용하여 clean 이라는 파일명을 가진 파일만 지워줍니다.

이 경우에는 가지치기를 하지 않고 계속 완전탐색을 해주셔야합니다.

 

 

 

 

 

이 케이스에서 cleanup.IN2 or cleanup.IN2* 명령어를 사용해서 파일을 제거합니다.

 

 

 

 

 

이 케이스에서도 cleanup.IN1 or cleanup.IN1* 명령어를 사용해서 파일을 제거합니다.

 

 

 

 

 

 

이 경우에 cleanup.o* 명령어를 사용하여 파일을 제거하고 가지치기를 해줍니다.

 

 

정리하면 아래와 같습니다.

지워야 하는 문자열의 끝에 도달하면 명령어2번을 사용하여 해당 파일을 삭제한다.(가지치기 X, 계속 완전탐색 진행)

지우면 안되는 제약이 없는 경우 명령어1번을 사용해여 해당 파일 또는 해당 파일명 하위 노드들을 모두 삭제한다.(가지치기)

제거할 파일이 없는 경우 해당 노드부터는 탐색하지 않는다.(가지치기)

 

지우면 안되는 제약의 경우 forbidden 변수를 두어 판별하였습니다.

 

전체 코드는 아래와 같습니다.

#include <iostream>
#include <string>
using namespace std;

int T;
int answer = 0;

struct TRIE {
	bool targetFinish;
	bool forbidddenFinish;

	bool target;
	bool forbidden;

	char current;
	TRIE* Node[150];
	TRIE() {
		targetFinish = false;
		forbidddenFinish = false;
		target = false;
		forbidden = false;
		for (int i = 0; i < 150; i++) {
			Node[i] = NULL;
		}
	}

	~TRIE() {
		for (int i = 0; i < 150; i++) {
			if (Node[i] != NULL)
				delete Node[i];
		}
	}

	void insert(const char* str, bool isTarget) {
		if (isTarget) {
			target = true;
		}
		else {
			forbidden = true;
		}

		if (*str == NULL) {
			if (isTarget) {
				targetFinish = true;
				return;
			}
			else {
				forbidddenFinish = true;
				return;
			}
		}

		int next = *str;
		if (Node[next] == NULL) {
			Node[next] = new TRIE();
		}
		Node[next]->current = *str;
		Node[next]->insert(str + 1, isTarget);
	}

	void Find() {
		if (targetFinish) {
			answer++;
		}
		else if (!forbidden) {
			answer++;
		}

		if (forbidden) {
			for (int i = 'a'; i <= 'z'; i++) {
				if (Node[i] != NULL) {
					if (Node[i]->target == true) {
						Node[i]->Find();
					}
				}
			}
			for (int i = 'A'; i <= 'Z'; i++) {
				if (Node[i] != NULL) {
					if (Node[i]->target == true) {
						Node[i]->Find();
					}
				}
			}
			for (int i = '0'; i <= '9'; i++) {
				if (Node[i] != NULL) {
					if (Node[i]->target == true) {
						Node[i]->Find();
					}
				}
			}

			if (Node['.'] != NULL) {
				if (Node['.']->target == true) {
					Node['.']->Find();
				}
			}
		}
	}
};

int main() {
	cin >> T;

	for (int t = 0; t < T; t++) {
		TRIE* Root = new TRIE();

		int A;
		cin >> A;

		string input;
		for (int i = 0; i < A; i++) {
			cin >> input;
			Root->insert(input.c_str(), true);
		}

		int B;
		cin >> B;
		for (int i = 0; i < B; i++) {
			cin >> input;
			Root->insert(input.c_str(), false);
		}

		Root->Find();

		cout << answer << endl;
		answer = 0;
		delete Root;
	}

	return 0;
}