백준 11725 - 트리의 부모찾기 (BFS) JS

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

해당 문제는 그 말마따나 각 노드의 부모 노드를 구하는 문제다.

이 문제를 해결하기 위해 먼저 그래프를 구현한 다음,

너비우선탐색(BFS) 방식을 활용하여 1번 노드부터 차근차근 정답을 찾아나가고자 하였다.

 

그래프 구현 로직은 다음과 같다.

// 노드의 갯수만큼 배열을 생성하고
const graph = Array.from({length : +N+1}, ()=> [])
data.forEach((el)=> {
  // 연결된 노드를 그래프에 추가한다
  const [to,from] = el.split(' ').map(Number)
  graph[to].push(from)
  graph[from].push(to)
})

// 입력 예시대로 입력했을 경우 출력되는 값은 다음과 같다

[
  [],		// 0
  [ 6, 4 ],	// 1
  [ 4 ],	// 2
  [ 6, 5 ],	// 3
  [ 1, 2, 7 ], 	// 4
  [ 3 ],	// 5
  [ 1, 3 ],	// 6
  [ 4 ]		// 7
]

그리고 위에서 산출된 그래프를 시각화하면 다음과 같다.

이후 해당 그래프를 BFS 방식대로

1 => 4,6 => 2,7,3 => 5 순으로 node를 순회하며 결괏값을 채울 수 있게 로직을 구현해주면 된다.

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

const N = input.shift()
function solution(data) {
  // 앞에서 언급
  const graph = Array.from({length : +N+1}, ()=> [])
  data.forEach((el)=> {
    const [to,from] = el.split(' ').map(Number)
    graph[to].push(from)
    graph[from].push(to)
  })

  // 결괏값을 담을 배열
  const result = Array.from({length : +N+1}, ()=> 0)
  // 노드 1은 출력하지 않을 뿐더러, 정점이기 때문에 true값을 부여했다
  result[1] = true

  const BFS = (start) => {
    let queue = [start]

    while(queue.length) {
      const node = queue.shift()
      // 해당 node가 가진 graph 배열을 반복문으로 순회
      for(let i = 0 ; i < graph[node].length ; i++) {
        const nextNode = graph[node][i]
        // result[nextNode]에 값이 입력되지 않은 경우,
        // result[nextNode]에 부모 노드인 node를 할당해준 뒤 queue에 다음 노드로 추가
        if(!result[nextNode]) {
          result[nextNode] = node
          queue.push(nextNode)
        }
      }
    }
  }

  // 시작 노드 1을 초기값으로 대입했다
  BFS(1)

  console.log(result.slice(2).join('\n'))
}

solution(input)