[Algorithm] C++/Python 백준 14725번 : 개미굴

1
2
3
4
5

4
2 KIWI BANANA
2 KIWI APPLE
2 APPLE APPLE
3 APPLE BANANA KIWI

1
2
3
4
5
6
7

APPLE
--APPLE
--BANANA
----KIWI
KIWI
--APPLE
--BANANA

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

// 출처: https://www.acmicpc.net/problem/14725
// 42jerrykim.github.io에서 더 많은 정보를 확인할 수 있다.
#include <iostream>
#include <map>
#include <vector>
#include <string>
using namespace std;

// Trie의 노드 구조체 정의
struct Node {
    map<string, Node*> children; // 자식 노드들을 사전 순으로 저장
};

// Trie에 먹이 정보를 삽입하는 함수
void insert(Node* root, const vector<string>& foods) {
    Node* current = root;
    for (const string& food : foods) {
        // 자식 노드에 해당 먹이 이름이 없으면 새로 생성
        if (current->children.find(food) == current->children.end()) {
            current->children[food] = new Node();
        }
        // 현재 노드를 자식 노드로 이동
        current = current->children[food];
    }
}

// Trie를 DFS로 탐색하며 개미굴 구조를 출력하는 함수
void dfs(Node* node, int depth) {
    for (const auto& child : node->children) {
        // 현재 깊이에 따라 '--'를 출력하여 들여쓰기 구현
        for (int i = 0; i < depth; ++i) {
            cout << "--";
        }
        // 먹이 이름 출력
        cout << child.first << '\n';
        // 재귀적으로 자식 노드 방문
        dfs(child.second, depth + 1);
    }
}

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

    int N; // 로봇 개미의 수
    cin >> N;
    Node* root = new Node(); // Trie의 루트 노드 생성

    for (int i = 0; i < N; ++i) {
        int K; // 먹이 정보의 개수
        cin >> K;
        vector<string> foods(K);
        for (int j = 0; j < K; ++j) {
            cin >> foods[j]; // 먹이 이름 입력
        }
        insert(root, foods); // Trie에 먹이 정보 삽입
    }

    dfs(root, 0); // Trie 탐색 및 출력

    return 0;
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105

// 출처: https://www.acmicpc.net/problem/14725
// 42jerrykim.github.io에서 더 많은 정보를 확인할 수 있다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Trie의 노드 구조체 정의
typedef struct Node {
    char* food; // 현재 노드의 먹이 이름
    struct Node** children; // 자식 노드들
    int childCount; // 자식 노드의 수
    int capacity; // 자식 노드 배열의 용량
} Node;

// 노드 생성 함수
Node* createNode(char* food) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->food = food ? strdup(food) : NULL;
    node->children = NULL;
    node->childCount = 0;
    node->capacity = 0;
    return node;
}

// 자식 노드 추가 함수
void addChild(Node* parent, Node* child) {
    // 자식 노드 배열 확장
    if (parent->childCount == parent->capacity) {
        parent->capacity = parent->capacity ? parent->capacity * 2 : 4;
        parent->children = (Node**)realloc(parent->children, sizeof(Node*) * parent->capacity);
    }
    // 자식 노드 추가
    parent->children[parent->childCount++] = child;
}

// 자식 노드들 정렬 함수
int compare(const void* a, const void* b) {
    Node* nodeA = *(Node**)a;
    Node* nodeB = *(Node**)b;
    return strcmp(nodeA->food, nodeB->food);
}

// Trie에 먹이 정보를 삽입하는 함수
void insert(Node* root, char foods[][16], int k) {
    Node* current = root;
    for (int i = 0; i < k; ++i) {
        int found = 0;
        for (int j = 0; j < current->childCount; ++j) {
            if (strcmp(current->children[j]->food, foods[i]) == 0) {
                current = current->children[j];
                found = 1;
                break;
            }
        }
        if (!found) {
            Node* child = createNode(foods[i]);
            addChild(current, child);
            current = child;
        }
    }
}

// Trie를 DFS로 탐색하며 개미굴 구조를 출력하는 함수
void dfs(Node* node, int depth) {
    // 자식 노드들 정렬
    qsort(node->children, node->childCount, sizeof(Node*), compare);
    for (int i = 0; i < node->childCount; ++i) {
        for (int j = 0; j < depth; ++j) {
            printf("--");
        }
        printf("%s\n", node->children[i]->food);
        dfs(node->children[i], depth + 1);
    }
}

// 메모리 해제 함수
void freeNode(Node* node) {
    for (int i = 0; i < node->childCount; ++i) {
        freeNode(node->children[i]);
    }
    free(node->food);
    free(node->children);
    free(node);
}

int main() {
    int N;
    scanf("%d", &N);
    Node* root = createNode(NULL);

    for (int i = 0; i < N; ++i) {
        int K;
        scanf("%d", &K);
        char foods[15][16];
        for (int j = 0; j < K; ++j) {
            scanf("%s", foods[j]);
        }
        insert(root, foods, K);
    }

    dfs(root, 0);
    freeNode(root);

    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# 출처: https://www.acmicpc.net/problem/14725
# 42jerrykim.github.io에서 더 많은 정보를 확인할 수 있다.
import sys
sys.setrecursionlimit(10**6)

class Node:
    def __init__(self):
        self.children = {}

def insert(root, foods):
    current = root
    for food in foods:
        if food not in current.children:
            current.children[food] = Node()
        current = current.children[food]

def dfs(node, depth):
    for food in sorted(node.children.keys()):
        print('--' * depth + food)
        dfs(node.children[food], depth + 1)

def main():
    N = int(sys.stdin.readline())
    root = Node()
    for _ in range(N):
        inputs = sys.stdin.readline().split()
        K = int(inputs[0])
        foods = inputs[1:]
        insert(root, foods)
    dfs(root, 0)

if __name__ == "__main__":
    main()