[백준,c++] 22860번 - 폴더 정리 (small)

문제

22860번: 폴더 정리 (small)

 

코드

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

using namespace std;

int N, M;
unordered_map<string, vector<pair<int ,string>>> graph;
unordered_map<string, int> visited;
int file_cnt, file_type_cnt;

void dfs(string node){
    for(auto it: graph[node]){
        if(it.first == 0){
            if(!visited[it.second]){
                visited[it.second] = 1;
                file_type_cnt++;
            }
            file_cnt++;
        }
        if(it.first == 1){
            dfs(it.second);
        }
    }
}


vector<string> parsing(string s){
    vector<string> v;
    istringstream ss(s);
    string stringbuffer;
    
    while(getline(ss, stringbuffer, '/')){
        v.push_back(stringbuffer);
    }
    return v;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>N>>M;
    for(int i=0; i<N+M; i++){
        string P, E; int C; cin>>P>>E>>C;
        vector<pair<int ,string>> v = graph[P];
        v.push_back({C, E});
        graph[P] = v;
    }
    int Q; cin>>Q;
    for(int i=0; i<Q; i++){
        string s; cin>>s;
        vector<string> v = parsing(s);
        dfs(v.back());
        cout<<file_type_cnt << ' '<< file_cnt << '\n';
        file_cnt = 0;
        file_type_cnt = 0;
        visited.clear();
    }
}

 

풀이

dfs문제인데, 노드의 정보들을 map을 잘 활용해서 저장해야 하는 문제입니다. 

노드의 정보를 저장하는 부분은 다음과 같습니다. unordered_map<string, vector<pair<int ,string>>> graph;

3 4
main FolderA 1
main FolderB 1
FolderA File1 0
FolderA File2 0
FolderB FolderC 1
FolderB File1 0
FolderB File3 0

다음 입출력을 예시로 들어 graph에 저장하면 다음과 같습니다.

• [main] = {{1, "FolderA"}, {1, "FolderB"}
• [FolderA] = {{0, "File1"}, {0, "File2"}}
• [FolderB] = {{1, "FolderC"}, {0, "File1}, {0, "File3"}}

그 후 dfs를 이용하여 폴더일경우 계속 진입하여 탐색하면서 파일의 개수를 찾아주면 됩니다.

시간 복잡도는 dfs: O(N), 쿼리 개수: O(Q) 이므로 O(N^2)이 소요됩니다.