[문제풀이] 7432번: 디스크 트리

[문제풀이] 7432번: 디스크 트리

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

문제유형

TRIE

Solution

#include <stdio.h>
#include <malloc.h>
 
int N;
typedef struct st
{
    int check;
    int isWord;
    struct st* next;
    struct st* child[80];
}NODE;
char idx[100] = "!#$%&'()-0123456789@ABCDEFGHIJKLMNOPQRSTUVWXYZ^_`{}~";
NODE root;
char str[80];
char print_str[500*800][10];
 
int index(char ch)
{
    int i;
    for (i = 0; idx[i] != ch; i++);
    return i;
}
 
void append_node(char* str, NODE* addr)
{
    NODE* cur = addr;
 
    for(;;)
    {    
        int num = index(*str);
        
        if (cur->child[num] == NULL)
        {
            NODE* node = (NODE*)calloc(1, sizeof(NODE));
            cur->child[num] = node;                
        }
        
        str++;
        cur = cur->child[num];
        
        if (*str == '\0')
        {
            cur->isWord = 1;
            break;
        }
        else if (*str == '\\')
        {
            cur->isWord = 1;
            if (cur->next == NULL)
            {
                NODE* node = (NODE*)calloc(1, sizeof(NODE));
                cur->next = node;
                append_node(str + 1, cur->next);
            }
            else if (cur->next)
            {
                append_node(str + 1, cur->next);
            }
            break;
        }
    }
    return;
}
 
void print_node(int cnt, int n, int dir, NODE* addr)
{
    int i;
    NODE* cur = addr;
    
    if (cur != 0 && cur->isWord)
    {
        for (register int d = 0; d < dir; d++) printf(" ");
        printf("%s\n", print_str[cnt]);
 
        if (cur->next)
        {
            print_node(cnt + 1, 0, dir + 1, cur->next);
        }
    }
    if (cur == 0) return;
    for (i = 0; i < 80; i++)
    {
        if (cur->child[i])
        {
            print_str[cnt][n] = idx[i];
            print_str[cnt][n + 1] = 0;
            print_node(cnt, n + 1, dir, cur->child[i]);
        }
    }
}
 
void inputData()
{
    scanf("%d", &N);
    for (register int i = 0; i < N; i++)
    {
        scanf("%s", str);
        append_node(str, &root);    
    }
}
 
int main()
{
    inputData();
    print_node(0, 0, 0, &root);
 
    return 0;
}