[BOJ/Gold 2] 백준 7432 디스크 트리(C++)

문제 링크

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

7432번: 디스크 트리

 

문제

갑자기 맥북이 상근이의 손에서 떨어졌고, 화면이 켜지지 않았다. AS센터에 문의해보니 수리비가 97만원이 나왔고, 상근이는 큰 혼란에 빠졌다. 돈도 중요하지만, 상근이는 그 속에 들어있는 파일이 걱정되기 시작했다. 다행히 상근이는 저장되어 있는 중요한 디렉토리의 전체 경로를 텍스트 파일로 따로 저장하고 있었다. 예를 들면, WINNT\SYSTEM32\CERTSRV\CERTCO~1\X86. 

상근이의 중요한 디렉토리의 전체 경로가 모두 주어졌을 때, 디렉토리 구조를 구해 보기 좋게 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 중요한 디렉토리 전체 경로의 개수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개 줄에는 디렉토리 경로가 주어진다. 경로는 한 줄로 이루어져 있으며, 공백을 포함하지 않는다. 경로는 80글자를 넘지 않으며, 디렉토리는 역슬래시(\)로 구분된다.

각 디렉토리의 이름은 1~8글자이며, 알파벳 대문자, 숫자, 특수 문자로 이루어져 있다. 디렉토리 이름에 들어있을 수 있는 특수문자는 !#$%&'()-@^_`{}~ 이다.

출력

디렉토리 구조를 보기 좋게 출력한다. 한 줄에 하나씩 디렉토리의 이름을 출력하며, 공백은 디렉토리 구조상에서 깊이를 의미한다. 각 서브 디렉토리는 사전순으로 출력해야 하며, 부모 디렉토리에서 출력한 공백의 개수보다 1개 많게 공백을 출력한다. 예제 출력을 보면서 형식을 참고하는 것이 좋다.

예제 입력 1

7
WINNT\SYSTEM32\CONFIG
GAMES
WINNT\DRIVERS
HOME
WIN\SOFT
GAMES\DRIVERS
WINNT\SYSTEM32\CERTSRV\CERTCO~1\X86

예제 출력 1

GAMES
 DRIVERS
HOME
WIN
 SOFT
WINNT
 DRIVERS
 SYSTEM32
  CERTSRV
   CERTCO~1
    X86
  CONFIG

알고리즘 분류

• 트라이

풀이

입력받는 N개의 데이터는 트라이를 구성하는 브랜치의 하나라고 생각하자.

모든 디렉토리는 최대 8자의 문자로 구성된 문자열이므로 key값을 문자열로, value값을 트라이의 포인터로 갖는 map을 자식 노드로써 구현한다.

N개의 데이터를 입력받아 트라이를 완성시켰다면 DFS를 통해서 첫 번째 브랜치부터 트라이를 이루는 모든 디렉토리를 출력하고, 이 때 깊이를 나타내는 매개변수 Depth를 추가하여 깊이를 기록해주고 깊이가 1 증가할 때마다 공백을 먼저 출력시켜준다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#define INF 1e9
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct TRIE{
    bool isEnd;
    map<string, TRIE*> Child;
    map<string, TRIE*>::iterator IT;

    TRIE() : isEnd(false) {}
    ~TRIE() {
        for (IT = Child.begin(); IT != Child.end(); IT++) {
            delete IT->second;
        }
    }

    void make_Directory(vector<string> Vec) {
        TRIE* NowTrie = this;

        for (int i = 0; i < Vec.size(); i++) {
            string Now = Vec[i];
            if (!NowTrie->Child[Now]) {
                NowTrie->Child[Now] = new TRIE;
            }
            NowTrie = NowTrie->Child[Now];
        }
        NowTrie->isEnd = true;
    }
};

int N, K;
string S;
vector<string> Directory;

vector<string> Split(string Str) {
    vector<string> Res;
    string tmp = "";
    for (int i = 0; i < Str.size(); i++) {
        if (Str[i] == '\\') {
            Res.push_back(tmp);
            tmp = "";
        }
        else {
            tmp += Str[i];
        }
    }
    Res.push_back(tmp);

    return Res;
}

void DFS(TRIE* Trie, int Depth) {
    map<string, TRIE*>::iterator IT;
    for (IT = Trie->Child.begin(); IT != Trie->Child.end(); IT++) {
        for (int i = 0; i < Depth; i++) {
            cout << " ";
        }
        cout << IT->first << "\n";
        DFS(IT->second, Depth + 1);
    }
}

void find_Answer(TRIE* Root) {
    DFS(Root, 0);
}

void input() {
    TRIE* Root = new TRIE();
    cin >> N;
    while (N--) {
        Directory.clear();
        cin >> S;
        Directory = Split(S);
        Root->make_Directory(Directory);
    };
    find_Answer(Root);
    delete Root;
}

int main() {
    FASTIO
    input();

    return 0;
}