촌수계산

• https://www.acmicpc.net/problem/2644

오늘의 학습 키워드

BFS

• 정점과 같은 레벨에 있는 노드(형제 노드)를 먼저 탐색하는 방식
• 큐 자료구조를 사용하여 인접한 정점들의 리스트를 관리한다

문제 해결 방법

• 인접 정점은 오름차순으로 방문한다
• 무방향 그래프이기 때문에, 그래프를 그릴 때 정점 u와 정점 v는 양방향임을 고려한다
• BFS를 활용해 문제를 해결한다
  1. 시작 노드를 큐에 넣고 방문 처리한다
  2. 큐에서 원소를 꺼내어 방문하지 않은 인접 노드가 있는지 확인한다
     • 있다면, 방문하지 않은 인접 노드를 큐에 모두 삽입하고 방문 처리한다
  3. 2번 과정을 더 이상 반복할 수 없을 때까지 반복한다.
• a에서 b까지 도달할 때 depth를 구하지만, 도달하지 못하고 while문을 빠져나올 경우 -1을 출력한다

코드

class Queue {
  constructor() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }
  enqueue(item) {
    this.items[this.tailIndex] = item;
    this.tailIndex += 1;
  }
  dequeue() {
    const item = this.items[this.headIndex];
    delete this.items[this.headIndex];
    this.headIndex += 1;
    return item;
  }
  peek() {
    return this.items[this.headIndex];
  }
  get length() {
    return this.tailIndex - this.headIndex;
  }
  get isEmpty() {
    return this.length === 0;
  }
}

// input
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");
const N = +input.shift();
const [a, b] = input.shift().split(" ").map(Number);
const M = +input.shift();
const relations = input.map((v) => v.split(" ").map(Number));

// G (graph)
const G = Array.from(new Array(N + 1), () => []);

relations.map(([u, v]) => {
  G[u].push(v);
  G[v].push(u);
});

G.map((node) => node.sort((a, b) => a - b));

// BFS
function bfs(start, target) {
  const visited = Array(N + 1).fill(false);
  const Q = new Queue();

  Q.enqueue([start, 0]);
  visited[start] = true;

  while (!Q.isEmpty) {
    const [person, depth] = Q.dequeue();
    if (person === target) return depth;

    G[person].forEach((next) => {
      if (!visited[next]) {
        visited[next] = true;
        Q.enqueue([next, depth + 1]);
      }
    });
  }
  return -1;
}

// output
console.log(bfs(a, b));