[백준 P7432] 디스크 트리 Java

P7432 디스크 트리

7432번: 디스크 트리

 

문제

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

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

 

입력값

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

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

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

 

알고리즘

트라이를 활용하면 쉽게 풀 수 있다. 트라이가 무엇인지 모른다면 아래의 글을 미리 읽어보길 바란다.

트라이(Trie) 자료구조

 

그리고 이 문제는 백준의 개미굴 문제와 비슷하다. 아직 문제를 풀지 않았다면 아래 문제도 한 번 풀어보길 바란다.

[백준 P14725] 개미굴 Java

 

위의 블로그 글에서는 트라이의 각 노드에 문자를 저장했다. 이 문제에서는 트라이의 각 노드에 디렉토리 이름을 저장하면 된다. 즉, WINNT\SYSTEM32\CERTSRV라는 경로는 WINNT → SYSTEM32 → CERTSRV로 트라이에 저장하면 된다.

따라서 트라이의 자식을 저장하는 자료구조는 Map을 사용하여 디렉토리 명을 나타내는 문자열과 트라이를 매핑할 것이다. 각 서브 디렉토리는 사전순으로 출력되어야 하므로 Map에 넣어줄 때 순서를 맞추어주는 TreeMap을 사용하였다.

class Trie {
    Map<String, Trie> children;

    Trie() {
        children = new TreeMap<>();
    }
}

 

해당 문제는 특정 디렉토리가 존재하는지 여부를 질의하는 문제가 아니므로 isEnd 변수와 search 메서드는 필요하지 않다. (위의 블로그 글 참고) 따라서, isEnd 변수는 사용하지 않을 것이고 insert와 traverse만 사용하겠다. travsere를 하면서 트라이를 순회할 때 System.out.println문을 추가하여 디렉토리 구조를 출력하도록 했다.

public static void traverse(Trie current, String space) {
    for (Map.Entry<String, Trie> entry : current.children.entrySet()) {
        System.out.println(space + entry.getKey());
        traverse(entry.getValue(), space + " ");
    }
}

 

이 문제는 오히려 WINNT\SYSTEM32\CERTSRV 형식으로 들어오는 문자열을 split 할 때 어려웠다. 검색을 통해 Java는 “\\\\”를 작성해주면 \를 인식한다고 한다.

String[] paths = path.split("\\\\\\\\");

 

아래는 전체 코드이다.

 

코드

import java.util.*;
import java.io.*;

public class Main {
    static Trie root = new Trie();
    static int N;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++)
            insert(br.readLine());

        traverse(root, "");
    }

    public static void insert(String path) {
        Trie current = root;
        String[] paths = path.split("\\\\\\\\");

        for (int i = 0, size = paths.length; i < size; i++) {
            if (!current.children.containsKey(paths[i])) {
                current.children.put(paths[i], new Trie());
            }
            current = current.children.get(paths[i]);
        }
    }

    public static void traverse(Trie current, String space) {
        for (Map.Entry<String, Trie> entry : current.children.entrySet()) {
            System.out.println(space + entry.getKey());
            traverse(entry.getValue(), space + " ");
        }
    }
}

class Trie {
    Map<String, Trie> children;

    Trie() {
        children = new TreeMap<>();
    }
}