https://www.acmicpc.net/problem/7432
문제
> 갑자기 맥북이 상근이의 손에서 떨어졌고, 화면이 켜지지 않았다.
> AS센터에 문의해보니 수리비가 97만원이 나왔고, 상근이는 큰 혼란에 빠졌다.
> 돈도 중요하지만, 상근이는 그 속에 들어있는 파일이 걱정되기 시작했다.
> 다행히 상근이는 저장되어 있는 중요한 디렉토리의 전체 경로를 텍스트 파일로 따로 저장하고 있었다.
> 예를 들면, WINNT\SYSTEM32\CERTSRV\CERTCO~1\X86.
> 상근이의 중요한 디렉토리의 전체 경로가 모두 주어졌을 때,
디렉토리 구조를 구해 보기 좋게 출력하는 프로그램을 작성하시오.접근
트라이 알고리즘을 사용하여 디스크의 구조를 트리화 한다.
트리구조이므로 Node라는 구조를 정의하고 이는 map으로 자식의 정보를 가지는데 키값으로 자식 폴더의 이름을, 밸류값으로 자식 폴더의 주소값을 가진다.
이를 통해서 재귀구조로 이어진 자식들의 정보를 계속 가리키며 가진다.
이 구조를 이용해 경로를 입력받으면 이 경로를 \문자 기준으로 잘라서 차례로 저장한다.
문제해결
> 자식의 정보를 map을 이용해 key: 자식 폴더명, value:자식폴더 주소가지는 Node타입 구조체를 정의한다.
> 디시크의 최상위인 뿌리 경로를 root로 만든다.
> Node* root로 힙에 Node객체를 생성하고 root는 그 주소값을 가진다.
> 디스크 트리를 만드는 inputNode메서드를 정의한다. 매개변수로 입력받은 경로들을 받는다.
> 현재 위치를 나타낼 cur 포인터 변수를 만들고 초기값으로 root의 주소를 준다.
> 입력받은 경로들을 하나씩 보는데 현재 경로의 자식으로 해당 경로가 없으면 그 경로로 새로운 노드를 만든다.
> 만약 있다면 현재 경로를 그 경로로 이동 시킨다.
> 앞선 과정으로 정의 한 디스크 트리를 DFS를 통해 경로를 출력할 수 있도록 탐색하는 DFS를 정의한다.
> 매개변수로 특정 경로의 주소를 받고, depth 를 통해 재귀로 현재의 깊이를 나타낸다.
> 입력받은 주소값 node에 대해서 next를 통해 해당 node의 자식을 잡는다.
> next엔 child 즉, 자식의 이름과 주소가 잡혀있다.
> 이제 깊이마다 공백으로 표시하므로 depth의 수만큼 공백을 출력한 뒤, next.first로 자식의 이름을 출력한다.
> 재귀로 해당 자식의 주소와 depth + 1을 넘겨서 이어지는 자식을 볼 수 있게한다.
> main함수에선 N을 입력받고 N번 경로를 입력받는다.
> 경로를 한 문자씩 보며 tmp에 추가하다가 \기준으로 경로를 잘라 path벡터에 저장한다.
> 저장이 끝나면 inputNode메서드를 호출해서 해당 경로를 넣어서 트리 구조를 만든다.
> 다음 경로를 받기 전 path를 초기화해주고 또 입력받은 뒤 트리를 더 그려준다.
> DFS를 통해 만들어진 트리를 탐색해 경로를 출력한다.코드
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <string>
using namespace std;
int N;
struct Node {
map<string, Node*> child;
};
Node* root = new Node();
void InputNode(vector<string> path) {
Node* cur = root;
for (auto p : path) {
if (cur->child.find(p) == cur->child.end())
cur->child[p] = new Node();
cur = cur->child[p];
}
}
void DFS(Node* node, int depth) {
for (auto next : node->child) {
for (int i = 0; i < depth; i++) cout << " ";
cout << next.first << '\n';
DFS(next.second, depth + 1);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
while (N--) {
string str;
cin >> str;
vector<string> path;
string tmp = "";
for (int i = 0; i < str.length(); i++) {
if (str[i] == '\\') {
path.push_back(tmp);
tmp = "";
}
else {
tmp += str[i];
}
}
path.push_back(tmp);
tmp = "";
InputNode(path);
}
DFS(root, 0);
}
후기
포인터를 해본 경험이 많이 없어서 Node 타입선언과 접근들을 이해하는데 정말 어려웠다.
심지어 포인터 구조에 재귀까지 엮어져있어서 이해가 쉽지않았다.
