백준 14725: 개미굴 - javascript(문자열, 트리)

문제 출처 

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

 

정답 풀이 

문자열 문제를 풀고 싶었는데, 어쩌다 보니 트리 알고리즘을 연습하게 됐다. 

뭐, 잘됐다. 트리 문제는 한번 풀어본 것 같다..;; (아무래도 양심이 없다) 

 

트리 문제는 언제나 간단하게 생각하면 된다. 

- 트리를 어떻게 생성할까? 

- 트리를 어떻게 탐색할까? 

 

이 두개만 생각해주면 된다.

그러다 보니, 아래와 solution 함수가 쉬워진다. 

생성은 insert 를 통해, 

탐색은 print를 통해 구현하면 된다.  

 

## insert

 

path는 문제에서 주어진 값이 차례대로 들어갈 것이다. 

2 B A
4 A B C D
2 A C

 

내 전체 코드를 보면, 앞에 숫자는 slice(1)를 통해 없앴고, 배열로 구현해놨다. 

아래와 같은 모습이 되고, 각각의 배열이 path가 된다. 

[

[B,A]

[A,B,C,D]

[A,C]

]

 

만약 현재 rootNode에 path를 반복문 돌렸을 때의 각 node가 없다면 새롭게 Tree를 생성해주는 코드다. 

그리고 다음 node는 현재 Tree의 next가 된다. 

## print 

이제 print는 우리가 생성해준 트리를 문제가 원한대로 출력을 해줘야 한다. 

트리의 깊이? 여기서 indent에 따라 '-'의 개수가 결정된다. 

처음엔 0개 

다음엔 2개 

그다음엔 4개 

 

따라서 코드를 보면 indent가 +2개씩 늘어나는 것을 확인할 수 있다. 

 

그리고, 문제에서 문자 정렬대로 출력하기를 원했다. 따라서 현재 트리에서 next의 모든 노드의 key를 기준으로 정렬을 한다. 

그리고 그 해당 키를 출력 후, 해당 노드의 다음 노드로 바로 탐색을 들어간다. 

 

정답 코드 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const n = Number(input.shift()); 
let arr = []; 
for(let i=0; i<n; i++){
    arr.push(input[i].split(' ').slice(1))
}

 class Tree{
        constructor(val){
            this.val = val; 
            this.next = {}; 
        }
     
        insert(path){
            let current = this; 
            for(let node of path){
                if(!current.next[node]){
                    current.next[node] = new Tree(node); 
                }
                current = current.next[node]; 
            }
        }
        print(indent = 0){
            const keys = Object.keys(this.next).sort(); 
            for(let key of keys){
                console.log('-'.repeat(indent) + key); 
                this.next[key].print(indent+2)
            }
        }
    }

function solution(n,arr){
   let rootTree = new Tree('root'); 
    
    for(let i=0; i<n; i++){
        rootTree.insert(arr[i])
        }
        rootTree.print(); 
    }
    

solution(n,arr)