c언어 14725번 개미굴 (백준)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Trie {
    char data[16];
    struct Trie * next;
    struct Trie * child;
}Trie;

Trie * insert(Trie * root, char str[]) { //Trie 삽입
    Trie * newNode = malloc(sizeof(Trie)); //새로운 노드 만들고
    newNode->next = NULL; //초기화
    newNode->child = NULL; //초기화
    strcpy(newNode->data, str); //문자열 복사
    
    Trie * p = root->child; //루트의 자식 주소 복사
    Trie * bp = NULL; // before p //탐색과정에서 바로 이전에 다룬 노드의 주소 담는 변수
    
    if(p!=NULL) { //자식이 하나라도 있다!
        //exist?
        for(;p!=NULL;p=p->next) { //자식 탐색
            int tmp = strcmp(str, p->data); //우선순위 알아보기 str이 우선순위가 높다면 음수 값이다.
            if(tmp == 0) { //같다면, 중복이므로
                free(newNode); //새로 만들어논 노드는 필요없으니 동적할당 해제
                return p; //이미 있던 노드의 주소를 반환
            }
             else if(tmp < 0) { //현재 탐색하는 노드의 단어보다 우선순위가 빠르다면 
                //non exist, and it's small
                if(bp == NULL) root->child = newNode; //이게 자식들중 가장 우선순위가 빠른 경우
                else bp->next = newNode; //bp -> p     bp->newNode->p //앞에 더빠른 자식이 있는 경우
                newNode->next = p; //새로 만든 노드의 옆이 바로 지금 탐색하는 노드이다.
                return newNode; //새로 만든 노드의 주소값 반환
            }
            bp = p; //이전에 탐색한 노드의 주소값 갱신
        }
        //non exist, and it's most big 탐색이 끝났으나, 중복된 것이 없는 경우 우선순위가 가장 나중이다.
        bp->next = newNode; //가장 마지막에 탐색한 자식 뒤에 붙여준다.
        return newNode; 
        
    } else { //자식이 없다
        root->child = newNode; 
        return newNode; 
    } return NULL;
}

void find(Trie*root, int depth) { //dfs 출력
    for(Trie * p = root->child; p!=NULL; p=p->next) {
        for(int i=0; i<depth; i++) printf("--");
        printf("%s\n",p->data);
        find(p, depth+1);
    }
}

int main()
{
    int n,m;
    char str[16]={};
    Trie * root = (Trie*) malloc(sizeof(Trie));
    root->next = NULL;
    root->child = NULL;
    
    scanf("%d",&n); //테스크 케이스 몇개
    for(int i=0; i<n; i++) {
        scanf("%d",&m); //단어 몇개
        Trie * tmp = root;
        for(int j=0;j<m;j++) {
            scanf("%s",str); //단어를 하나씩 받은 다음
            tmp = insert(tmp, str); //Trie
        }
    }
    
    find(root, 0); //출력
    
    return 0;
}

 

풀이 : 트라이

 

0. 트라이의 노드를 의미하는 구조체를 만들고 트라이의 root을 만듭니다.

 

1. 단어들을 입력받으면 이것을 root의 자식에 넣습니다.

 1.1  만약 A, B이렇게 입력을 받았다면  root의 자식에 A,  A의 자식에 B을 넣는 방식입니다.

 1.2  만약 이미 같은 것이 들어있었다면, 중복으로 추가하는 것이 아닌, 이미 있던 노드의 주소를 반환합니다.

 1.3  오름차순 정렬을 해야하므로, 같은 것이 있는지를 확인해보면서, 만약 비교하던 것보다 우선순위가 빠르다면, 새로운  노드를 비교하던 것의 노드의 바로 앞에 만들어 줍니다.

 1.4 만약 같은것이 없었다면 뒷 부분에 새로 노드를 만들어 줍니다.

 1.5 그냥 자식이 없는 경우는 바로 노드만 만들어줍니다.

 

2. 탐색은 dfs 방식으로 합니다.

 

문자열을 다루기에 string.h 의 함수를 쓰면 편합니다.

우선순위는 strcmp(char * s1, char * s2); //s1 우선순위가 더 빠르면 음수, 같으면 0, 더 늘리면 양수

문자열 복사는 strcpy(char * destination, char * source);

 

 

C++이라면 vector등 STL로 쉽게 풀 수 있으며,

C언어의 경우 Trie을 구성할 구조체를 만든 다음, 이것들을 포인터를 이용하여 하나씩 연결해주면 됩니다.

 

이런식으로 각 노드는 옆을 가리키는 주소와, 자식을 가리키는 주소를 가지고 있으면 됩니다.