백준2644 - 촌수계산 (BFS) JS

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

문제는 각 node 간의 관계가 주어졌을 때, 특정 두 node의 촌수를 계산하는 문제다. (노드 간 거리 +1)

나는 그래프를 먼저 구현한 후, BFS를 활용하여 해결했다.

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

function solution(data) {
  const [N, temp, _, ...arr] = data
  // '촌수'를 구해야하는 두 노드
  const [target1,target2] = temp.split(' ').map(Number)
  
  // 그래프 구현
  const graph = Array.from({length : +N+1}, ()=> [])
  arr.forEach(el => {
    const [mother, son] = el.split(' ').map(Number)
    graph[mother].push(son)
    graph[son].push(mother)
  })
  
  const BFS = (startNode) => {
    // 이미 다녀온 경로를 사용하지 않기 위한 visited 배열
    const visited = []
    // queue의 요소로는 [노드 번호, 거리]를 담는다
    const queue = [[startNode,0]]

    while(queue.length) {
      // queue의 요소 가져오기
      const [node, times] = queue.shift()
      if(!visited.includes(node)) {
        visited.push(node)
        for(let i = 0 ; i < graph[node].length ; i ++) {
          // 요소가 target2 와 일치한 경우 거리 + 1 반환
          if(graph[node][i] === target2) return times + 1
          // 방문하지 않은 곳일 경우 queue에 추가
          if(!visited.includes(graph[node][i])) queue.push([graph[node][i], times + 1])
        }
      }
    }
    // queue가 빌 경우 -1 리턴 (이 경우는 주어진 타겟에 도달할 수 없는 경우)
    return -1
  }

  const result = BFS(target1)
  console.log(result)
}

solution(input)