백준14217 - 그래프 탐색 (BFS) node.js

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

자바스크립트로 풀이한 정답자가 없어서 포스팅하게 된 문제다.

여타 BFS 알고리즘 같이 루트 노드와 각 노드 사이의 최단 거리를 출력하는 문제지만, 다른 점이 있다면 간선을 추가 | 삭제를 할 수 있어야 문제 해결이 가능하다.

 

문제 해결 방식

BFS 알고리즘에 대한 내용은 많이 다뤘기 때문에, 간선을 추가 | 삭제하는 부분만 언급한다. 

입력값을 활용하여 상단의 로직으로 트리형 자료 구조를 만들었다고 했을 때, 이차원 배열로 트리 구조가 형성되게 된다.

이때, 간선을 삭제하는 경우에 있어, splice 메서드를 사용할지 filter 를 사용할지 고민을 했더랬다.

둘다, 시간 복잡도가 O(n)으로 동일하지만, splice의 경우 삭제할 원소의 Index 값을 알고 있어야 하며, 이를 알기 위해선 최대 시간복잡도가 O(n)인 indexOf 메서드를 선행적으로 사용해야 하기 때문에 보다 유리한 filter 메서드를 채택해 간선을 삭제했다.

(사실 그리 중요한 내용은 아니지만, 기록으로 남기고 싶었다...)

// 트리 생성
  const arr = data.map((el) => el.split(" ").map(Number));
  const [n, m] = arr.shift();
  const edges = arr.slice(0, m),
    testCase = arr.slice(m + 1);

  const trees = Array.from({ length: n + 1 }, () => []);

  edges.forEach(([a, b]) => {
    trees[a].push(b);
    trees[b].push(a);
  });

// 간선 추가 삭제
  function BFS([act, a, b]) {
  // 처음 주어지는 원소가 2면 간선 삭제 | 1이면 간선 추가
    if (act === 2) {
      trees[a] = trees[a].filter((el) => el != b);
      trees[b] = trees[b].filter((el) => el != a);
    } else {
      trees[a].push(b);
      trees[b].push(a);
    }
    
    // 중략 //

 

전체 소스 코드

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt")
  .toString()
  .trim()
  .split("\n");

function solution(data) {
  const arr = data.map((el) => el.split(" ").map(Number));
  const [n, m] = arr.shift();
  const edges = arr.slice(0, m),
    testCase = arr.slice(m + 1);

  const trees = Array.from({ length: n + 1 }, () => []);

  edges.forEach(([a, b]) => {
    trees[a].push(b);
    trees[b].push(a);
  });

  function BFS([act, a, b]) {
  // 처음 주어지는 원소가 2면 간선 삭제 | 1이면 간선 추가
    if (act === 2) {
      trees[a] = trees[a].filter((el) => el != b);
      trees[b] = trees[b].filter((el) => el != a);
    } else {
      trees[a].push(b);
      trees[b].push(a);
    }

    const distances = Array.from({ length: n + 1 }, () => -1);

    const queue = [[1, 0]];
    let queueIdx = 0;

    while (queueIdx < queue.length) {
      const [node, dist] = queue[queueIdx++];

      if (distances[node] !== -1) continue;
      distances[node] = dist;

      trees[node].forEach((next) => {
        if (distances[next] == -1) queue.push([next, dist + 1]);
      });
    }

    return distances.slice(1);
  }

  const result = testCase.map((el) => BFS(el));

  console.log(result.map((el) => el.join(" ")).join("\n"));
}

solution(input);