[baekjoon 22860] 폴더 정리(small) (DFS, BFS, 구현, HashMap) (C++)

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

22860번: 폴더 정리 (small)

이름이 main 폴더 안에 여러 가지 파일과 폴더가 존재한다.

위 구조는 main 폴더의 하위 구조를 계층적으로 표시한 것이다. FolderA, FolderB, FolderC는 폴더이고 File1, File2, File3은 파일이다. 파일 이름이 같은 경우는 동일한 파일이다.

한 폴더 안에는 같은 이름의 파일이 두 개 이상 존재할 수 없다.

main 하위 디렉토리에 같은 이름의 폴더가 두 개 이상 존재할 수 없다.

폴더 정리를 하기 위해 main 폴더 하위에 있는 파일들을 확인하려고 한다.

주어지는 쿼리에 대해 폴더와 파일의 정보를 알려주는 프로그램을 만들어보자.

---

나는 입력값(문자열)을 숫자로 바꿨고, 그 숫자들을 인접 리스트로 저장해서 그래프를 만들었다.

일단 다 넣어놓고, 폴더인지 파일인지는 check배열을 통해서 구분해주었다.

그리고 그 그래프를 root부터 DFS를 하면서 각 폴더의 파일 현황을 갖고 있는 HashMap을 만들어주었다.

 

1. name2int로 폴더, 파일 이름을 숫자로

2. 그러고 나서 입력값을 인접 리스트로 구성.

 

3. root인 main의 index를 받아서 DFS 수행

 

4. DFS 하면서 각 노드의 파일 정보를 담은 HashMap을 저장(DP처럼 저장해주었다.)

 

5. 쿼리를 돌면서 쿼리의 가장 마지막 폴더의 인덱스를 통해서 각 노드의 HashMap에서 개수를 세주기.

 

매 쿼리마다 그래프 탐색을 하면 비효율적일 것 같아서 DFS를 통해 vector<HashMap>에 저장해주었는데 풀이 중에 매번 BFS로 돌면서 개수를 세준 코드도 통과했다. 오히려 나보다 빨랐다.

 

+ 파일의 종류와, 개수를 세줘야 했기에 HashMap을 이용했다. map을 이용하면 종류는 map의 사이즈, 개수는 map 안의 개수를 다 더해주면 되기 때문이다.

#include <iostream>
#include <sstream>
#include <unordered_map>
#include <vector>

using namespace std;

int N, M, tag;
string from, to, route;
unordered_map<string, int> name2int;
bool isFile[2001];
vector<int> v[2001];
vector<unordered_map<int, int>> resultMap[2001];

unordered_map<int, int> DFS(int x) {
	unordered_map<int, int> result;
	for (int i = 0; i < v[x].size(); i++) {
		int nx = v[x][i];
		if (isFile[nx]) {
			result[nx]++;
			continue;
		}
		unordered_map<int, int> temp = DFS(nx);
	
		for (auto k : temp) {
			result[k.first] += k.second;
		}
	}
	resultMap[x].push_back(result);
	return result;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	int cnt = 1;
	for (int i = 0; i < N + M; i++) {
		cin >> from >> to >> tag;
		if (name2int.find(from) == name2int.end()) {
			name2int[from] = cnt;
			cnt++;
		}
		if (name2int.find(to) == name2int.end()) {
			name2int[to] = cnt;
			cnt++;
		}
		v[name2int[from]].push_back(name2int[to]);
		if (tag == 0) { // folder to folder
			isFile[name2int[to]] = true;
		}
	}

	DFS(name2int["main"]);

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> route;
		string buffer;
		istringstream ss(route);

		while (getline(ss, buffer, '/')) {
		}
		unordered_map<int, int> temp = resultMap[name2int[buffer]][0];
		if (temp.size() == 0) {
			cout << 0 << " " << 0 << "\n";
			continue;
		}
		else {
			int cnt = 0;
			for (auto k : temp) {
				cnt += k.second;
			}
			cout << temp.size() << " " << cnt << "\n";
		}
	}
}