[C++] 백준 22860번: 폴더 정리 (small)

문제 링크

22860번: 폴더 정리 (small)

문제 요약

폴더와 폴더에 속해 있는 폴더 또는 파일 쌍이 주어진다. 이때 각 폴더의 경로를 쿼리로 받으면, 하위 경로 상의 파일 종류의 수, 파일의 수를 출력해야 한다.

접근 방법

골드3치고는 너무 쉬운 문제라고 생각합니다.

처음에는 깔끔하게 전처리로 값을 모두 구해놓고 매 쿼리마다 저장된 값만 출력하고자 했으나, 코드가 조금 지저분해지는거 같아서 그냥 다른 풀이를 택했습니다.

기본적인 접근 방법은 입력을 그래프로 잘 저장받은 다음, 매 쿼리마다 DFS 또는 BFS를 돌려주면 됩니다. 파일 수 N, 폴더 수 M의 합이 2000밖에 안되고, 질의 수 Q도 1000개밖에 안되기 때문에 $(N + M) \times Q$는 해봐야 2백만밖에 되지 않습니다.

const int MAX = 2001;
bool is_directory[MAX];
vector<int> adj[MAX];
unordered_map<string, int> um;

int insert(const string &str) {
    static int idx = 1;

    if (um.find(str) == um.end()) {
        um.insert({str, idx});
        return idx++;
    } else {
        return um[str];
    }
}

int main() {
    int n, m;
    cin >> n >> m;

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

        cin >> p >> f >> c;

        int pp = insert(p);
        int ff = insert(f);

        is_directory[ff] = c;

        adj[pp].push_back(ff);
    }
}

입력을 받을때 파일명 또는 폴더명을 해시맵에서 검색해서, 맵 내부에 없다면 1씩 증가시키면서 번호를 부여합니다. 그리고 인접리스트를 이용해 이 번호를 바탕으로 방향 그래프를 만들어 줍니다. 또 그래프 탐색을 할때, 파일인지 폴더인지 알아야 하기 때문에 bool 배열에 그 여부도 저장해줍니다.

이제 각 쿼리가 주어지면, 맨 마지막 폴더명만 파싱해주고, 해시맵에서 폴더명의 인덱스를 얻은 다음에 거기서부터 DFS를 돌면서 파일의 수와 파일 종류의 수를 세주면 됩니다.

BFS를 사용하면 그냥 셋과 cnt 변수를 하나 써주면 되고, DFS를 사용한다면 전역변수 또는 static 변수로 셋과 cnt 변수를 써주면 됩니다.

저는 static 변수로 처리했습니다.

코드

#include <bits/stdc++.h>

using namespace std;

const int MAX = 2001;
bool is_directory[MAX];
vector<int> adj[MAX];
unordered_map<string, int> um;

int insert(const string &str) {
    static int idx = 1;

    if (um.find(str) == um.end()) {
        um.insert({str, idx});
        return idx++;
    } else {
        return um[str];
    }
}

pair<int, int> dfs(int now, int start) {
    static unordered_set<int> us;
    static int cnt;

    if(now == start) {
        us.clear();
        cnt = 0;
    }

    for (auto &next: adj[now]) {
        if(!is_directory[next]){
            us.insert(next);
            cnt++;
            continue;
        }

        dfs(next, start);
    }

    return {us.size(), cnt};
}

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

    int n, m;
    cin >> n >> m;

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

        cin >> p >> f >> c;

        int pp = insert(p);
        int ff = insert(f);

        is_directory[ff] = c;

        adj[pp].push_back(ff);
    }

    int q;
    cin >> q;

    while(q--) {
        string query;
        cin >> query;

        string tmp = "";
        for(auto& i : query) {
            if (isalpha(i)) {
                tmp.push_back(i);
            } else {
                tmp.clear();
            }
        }

        int start = um[tmp];
        auto ans = dfs(start, start);
        cout << ans.first << ' ' << ans.second << '\n';
    }

    return 0;
}