[BaekJoon] 14725번 - 개미굴 [Java][C++]

문제 링크

---

1. 문제 풀이

로봇 개미로 개미굴을 탐사한 결과를 출력하는 문제로 탐사는 문자열의 사전순으로 DFS 스타일로 탐사를 해야한다. 주어진 개미굴을 트라이 자료구조를 활용해서 저장하면 해결할 수 있는데 각 노드가 문자 하나가 아닌 단어를 저장하는 방식으로 하면 된다. 이를 위해 트리맵 배열을 활용해서 배열 인덱스에 노드 번호, 트리맵의 키에 단어, 값에 노드 번호가 오도록 했다. 이러면 현재 노드의 번호를 cur, 트리맵 배열을 nxt라고 할 때, nxt[cur]로 현재 노드의 다음 노드들의 단어와 번호를 가진 트리맵을 얻을 수 있다.

예제 입력 2를 예로 들면 아래와 같이 된다.

출력의 경우 DFS를 통해 해주면 되며 루트부터 재귀 깊이 0으로 탐색을 시작하면 된다. 현재 노드 번호를 통해 얻은 트리맵에서 재귀 깊이에 맞춰 하이픈을 출력후 단어를 출력하고 해당 단어의 번호를 재귀로 넘기면 된다.

---

2. 코드

1. 풀이 [Java]

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

public class Main {

    static StringBuilder sb = new StringBuilder();
    static final int MX = 1 + 1000 * 15;
    static final int ROOT = 0;
    static int unused = ROOT + 1;
    static Map<String, Integer>[] nxt = new TreeMap[MX];

    static {
        for (int i = 0; i < MX; i++) {
            nxt[i] = new TreeMap<>();
        }
    }

    static void insert(String[] words) {
        int cur = ROOT;
        for (String word : words) {
            if (!nxt[cur].containsKey(word)) nxt[cur].put(word, unused++);
            cur = nxt[cur].get(word);
        }
    }

    static void dfs(int cur, int depth) {
        for (Map.Entry<String, Integer> entry : nxt[cur].entrySet()) {
            sb.append("--".repeat(depth)).append(entry.getKey()).append("\n");
            dfs(entry.getValue(), depth + 1);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        while (n-- > 0) {
            st = new StringTokenizer(br.readLine());
            int k = Integer.parseInt(st.nextToken());

            String[] words = new String[k];
            for (int i = 0; i < k; i++) {
                words[i] = st.nextToken();
            }
            insert(words);
        }

        dfs(ROOT, 0);

        System.out.println(sb);
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

const int MX = 1 + 1000 * 15;
const int ROOT = 0;
int unused = ROOT + 1;
map<string, int> nxt[MX];

void insert(auto& v) {
    int cur = ROOT;
    for (string& s : v) {
        if (nxt[cur][s] == 0) nxt[cur][s] = unused++;
        cur = nxt[cur][s];
    }
}

void print(int cur, int depth) {
    for (auto& [k, v] : nxt[cur]) {
        for (int i = 0; i < depth; i++) {
            cout << "--";
        }
        cout << k << '\n';
        print(v, depth + 1);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    while (n--) {
        int k;
        cin >> k;

        vector<string> v(k);
        for (string& s : v) cin >> s;

        insert(v);
    }

    print(ROOT, 0);
}

---