99클럽 코테 스터디 17일차 TIL - 너구리구구 (그래프/bfs)

문제: https://www.acmicpc.net/problem/18126

접근방식

• 입구(1번 방)에서 시작해서 모든 방까지의 거리를 계산한 후 그 중 가장 큰 값을 찾기
  • 입력을 받아 그래프(트리) 구조를 만들고 BFS를 사용해 입구에서 각 방까지의 거리를 계산한 다음, 계산된 거리 중 가장 큰 값을 출력

구현

const fs = require('fs')
const [N, ...arr] = fs.readFileSync('/dev/stdin').toString().trim().split('\n')
const n = Number(N)

function solve() {
  if (n === 1) { // 방이 하나뿐이면 입구에서 가장 먼 방도 입구 자신이므로 거리는 0
    console.log(0)
    return
  }

  const graph = Array(n + 1)
    .fill()
    .map(() => [])

  for (let i = 0; i < arr.length; i++) {
    const [a, b, c] = arr[i].split(' ').map(Number)
    // 양방향으로 연결
    graph[a].push({ to: b, distance: c })
    graph[b].push({ to: a, distance: c })
  }

  function bfs(start) {
    const distances = Array(n + 1).fill(-1)
    distances[start] = 0

    const queue = [{ room: start, distance: 0 }]

    while (queue.length > 0) {
      const { room, distance } = queue.shift()

      for (const neighbor of graph[room]) {
        if (distances[neighbor.to] === -1) {
          const newDistance = distance + neighbor.distance
          distances[neighbor.to] = newDistance
          queue.push({ room: neighbor.to, distance: newDistance })
        }
      }
    }

    return Math.max(...distances)
  }

  console.log(bfs(1))
}

solve()