[백준/BOJ] 백준 22860번 : 폴더 정리 (small)

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

22860번: 폴더 정리 (small)

 

폴더에 폴더 아이디를 부여해서, 폴더 아이디로 폴더의 구조를 그래프로 표현했고, 파일에도 파일의 아이디를 부여해서 폴더에 있는 파일의 정보를 비트로 표현했다(ex 폴더에 1번, 2번 아이디의 파일이 있다면 00110으로 표현).

그리고 쿼리에 따라 해당 폴더부터 탐색을 시작해서 위에서 저장한 정보를 이용해 문제를 해결했다. 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <bitset>
using namespace std;

int n, m;
map<string, int> folder_id; //[폴더 이름] = 부여된 번호
int folder_id_cnt = 0;
map<string, int> file_id; //[파일 이름] = 부여된 번호
int file_id_cnt = 0;
vector<int> adj[1005]; //폴더로 이루어진 그래프
bitset<1005> folder_file[1005]; //해당 폴더에 있는 파일 정보 (ex 폴더에 1번,2번 파일이 있다면 0110로 표현)
int q;

//here 폴더 하위의 파일의 종류 정보와, here 폴더 하위의 파일 총 개수 반환
pair<bitset<1005>, int> Solve(int here) {

	bitset<1005> ret1 = folder_file[here];
	int ret2 = folder_file[here].count();

	for (int i = 0; i < adj[here].size(); i++) {
		int there = adj[here][i];
		pair<bitset<1005>, int> there_ret = Solve(there);

		ret1 |= there_ret.first;
		ret2 += there_ret.second;
	}

	return make_pair(ret1, ret2);
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;

	for (int i = 0; i < n + m; i++) {
		string p, f;
		int p_id, f_id;
		int c;

		cin >> p >> f >> c;

		if (folder_id.count(p) == 0) {
			folder_id_cnt++;
			folder_id.insert(make_pair(p, folder_id_cnt));
		}

		if (c == 1) { //f가 폴더일때

			if (folder_id.count(f) == 0) {
				folder_id_cnt++;
				folder_id.insert(make_pair(f, folder_id_cnt));
			}

			p_id = folder_id[p];
			f_id = folder_id[f];
			adj[p_id].push_back(f_id); //폴더 그래프에 추가
		}

		else { //f가 파일일때

			if (file_id.count(f) == 0) {
				file_id_cnt++;
				file_id.insert(make_pair(f, file_id_cnt));
			}

			p_id = folder_id[p];
			f_id = file_id[f];

			bitset<1005> file_status(0);
			file_status.set(f_id); //해당 파일 번호를 비트로 표시

			folder_file[p_id] = folder_file[p_id] | file_status; //해당 폴더에 존재하는 파일 상태 업데이트
		}
	}

	cin >> q;

	for (int i = 0; i < q; i++) {
		string input;
		cin >> input;

		string folder_name;
		int this_folder_id;

		if (input.rfind("/") == string::npos) {
			folder_name = input;
		}
		else {
			int index = input.rfind("/");
			folder_name = input.substr(index + 1, input.size() - (index + 1));
		}

		this_folder_id = folder_id[folder_name];
		pair<bitset<1005>, int> result = Solve(this_folder_id);
		cout << result.first.count() << " " << result.second << "\n";
	}

	return 0;
}