프로그래머스 - Lv.3 가장 먼 노드 (BFS) JS

https://school.programmers.co.kr/learn/courses/30/lessons/49189

 

 

해당 문제는 문제 제목 말마따나, 루트 노트인 1에서 가장 먼 노드의 갯수를 찾는 문제다.

 

가장 거리가 먼 노드를 찾는 것이기에, DFS보다는 BFS가 더 문제 의도와 적합하다고 생각해 BFS로 접근했다.

2023.06.01 - [개발/algorithm] - 프로그래머스 - 타겟넘버 / 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 구현 방식 비교

 

생각한 풀이 방식은 다음과 같다.

각 노드끼리 이어진 그래프를 구현하고, [노드 번호, 거리] 를 인자로 하는 배열을 queue로 활용해 BFS 로직을 구현한다.

 

소스 코드 및 풀이

function solution(n, edge) {
  // 그래프 구현
  const graph = Array.from({length : n+1}, ()=> [])
  edge.forEach(el=> {
    const [from, to] = el
    graph[from].push(to)
    graph[to].push(from)
  })
  
  // 이때 distances 배열은 '방문여부'와 '거리'를 기록하는 역할을 한다
  // 0 인 경우 false 이므로 방문하지 않았음을, 
  // 0이 아닌 경우는 거리가 입력된 경우이므로 방문했음을 의미한다
  const distances = Array.from({length : n+1}, ()=> 0)
  
  const BFS = () => {
    // queue 에는 인자값으로 [node 번호, 거리] 
    // 이때 초기 거리값이 0이 아닌 1인 이유는 
    // 거릿값이 저장될 distances 배열의 초깃값이 0이기 때문이고
    // 이로 인해 node 1의 연산이 중복되지 않게끔 하기 위함
    const queue = [[1,1]]

    while(queue.length) {
      const [node, distance] = queue.shift()
      // distances[node]에 값이 있을 경우 패스
      if(distances[node]) continue

      // 값이 없을 경우 거릿값을 distances 배열에 대입
      distances[node] = distance
      
      // 해당 노드가 가진 graph를 가져와 배열로 추가
      for(let i = 0 ; i < graph[node].length ; i++) {
        if(distances[node][i]) continue
        else queue.push([graph[node][i], distance + 1])
      }
    }
  }

  BFS()

  // 가장 먼 노드이므로 distances 배열에서 가장 큰 수의 길이를 구해 리턴
  const result = distances.filter(x => x === Math.max(...distances))
  return result.length
}

 

BFS 알고리즘에 익숙해지다 보니 생각한대로 수월하게 풀 수 있게 되어 뿌듯했다.