[백준] 14725번: 개미굴 (Node.js)

 

접근방식

문제를 살펴보면 우선 각 경로가 트라이 자료구조로 이루어져 있는 것을 확인할 수 있습니다.

 

트라이 자료구조란?

검색을 빠르고 효율적으로 할 수 있도록 설계된 트리 기반 자료구조이며, 주로 단어 목록에서 단어를 검색하거나 자동 완성 기능, 사전 검색, 문자열 패턴 매칭 등에 사용됩니다.
여기서 중요한 점은 문자열을 트리 형태로 저장하고, 공통 접두사를 공유하여 중복된 데이터를 최소화하는 것입니다.

 

간단한 설명으로 시작하여 다시 진행해보자면, 이 문제에서 요구하는 주요 작업은 입력된 경로를 트라이에 삽입하는 것입니다.

 

예를 들어

2 KIWI BANANA 는 KIWI -> BANANA의 경로를 만드는 것으로 KIWI 아래에 BANANA가 있는 것이지요.

 

결국 트라이를 재귀적으로 호출하여 안쪽 depth 까지 --를 출력하여 계층구조를 만들면 되겠습니다.

 

 

풀이 ⏰

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

rl.on("line", function (line) {
  input.push(line.trim());
}).on("close", function () {
  // 첫째줄: 경로의 수
  const num = parseInt(input[0]);
  // 트라이 자료구조의 루트 노드 (빈 객체)
  const trie = {};

  for (let i = 1; i <= num; i++) {
    // 첫째줄을 제외한 나머지 값 배열로 만들기
    const [, ...route] = input[i].split(" ");
    // 트라이에 경로 삽입
    insert(trie, route);
  }
  submit(trie, 0);
});

function insert(trie, route) {
  // 루트 객체 생성
  // obj가 trie의 루트객체를 참조(가리키고)하고 있음
  let obj = trie;
  for (let i of route) {
    // 빈 객체 안에 일치되는 값이 없으면 / 최초 실행 시 obj = {}
    // obj에 예를 들어 "KIWI"와 같은 문자열을 키값으로 가지는 빈객체 생성
    if (!obj[i]) {
      obj[i] = {};
    }
    // obj를 obj[i]가 가리키는 {}값을 바라보게함
    // 예를 들어 [ 'KIWI', 'BANANA' ]로 최초 실행 시 현재 obj는 { KIWI: { } } 의 KIWI쪽을 바라보고 있기에 빈객체로 보임
    // 두번째 실행시 { KIWI: { BANANA: { } } } 의 BANANA쪽을 바라보고 있기에 빈객체로 보임
    obj = obj[i];
  }
}

function submit(trie, depth) {
  // 각 키값들을 알파벳순으로 sort
  let arr = Object.keys(trie).sort();
  // 0번째는 repeat실행 x
  arr.forEach((item) => {
    console.log(`${"--".repeat(depth)}${item}`);
    // 재귀함수를 통해 트라이구조의 마지막depth까지 재귀호출
    submit(trie[item], depth + 1);
  });
}

 

백준 14725번 링크

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