[프로그래머스] 가장 먼 노드 (javascript)

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

프로그래머스

 

 

🤔 해결방법

1. 각 노드와 연결된 노드들의 리스트로 그래프 생성

2. BFS를 수행하면서 각 노드까지의 최단 거리를 distances 배열에 저장하고 최대값 개수를 반환

 

 

🔑 풀이

bfs로 풀어야 하는 문제라는 생각이 들어 지난번에 백준 DFS와 BFS 문제를 풀 때 정리해논 bfs 기본 코드를 긁어왔다.

 

BFS 기본 코드

// 방문한 정점을 저장하기 위한 배열
    const visited = [];

    // BFS 함수
    function bfs(node) {
      const queue = []; // 큐를 초기화
      queue.push(node); // 시작 정점을 큐에 추가
      visited[node] = true; // 시작 정점을 방문한 것으로 표시

      while (queue.length > 0) {
        const currentNode = queue.shift(); // 큐에서 정점을 하나 꺼내
        console.log(`방문한 정점: ${currentNode}`); // 현재 정점 처리 (출력 등)

        for (const adjacentNode of graph[currentNode]) {
          // 현재 정점과 인접한 모든 정점에 대해서:
          if (!visited[adjacentNode]) {
            queue.push(adjacentNode); // 방문하지 않은 정점이라면 큐에 추가
            visited[adjacentNode] = true; // 방문한 것으로 표시
          }
        }
      }
    }

 

bfs함수에서 거리를 기록하는 배열 distances 만 추가하고 distances를 리턴하도록 해줬다.

이후 노드 1부터 bfs를 돌리고 distances의 최대값 개수를 출력하면 된다.

최종 코드는 다음과 같다.

// BFS 함수
  function bfs(node, graph) {
    let visited = []; // 방문한 정점을 저장하기 위한 배열
    let distances = Array(graph.length).fill(0); // 거리를 저장하기 위한 배열
    let queue = []; // 큐를 초기화

    queue.push(node); // 시작 정점을 큐에 추가
    visited[node] = true; // 시작 정점을 방문한 것으로 표시
    distances[node] = 0; // 시작 노드의 거리는 0

    while (queue.length > 0) {
      const currentNode = queue.shift(); // 큐에서 정점을 하나 꺼내

      for (const adjacentNode of graph[currentNode]) {
        // 현재 정점과 인접한 모든 정점에 대해서
        if (!visited[adjacentNode]) {
          queue.push(adjacentNode); // 방문하지 않은 정점이라면 큐에 추가
          visited[adjacentNode] = true; // 방문한 것으로 표시
          distances[adjacentNode] = distances[currentNode] + 1; // 현재 노드의 거리 + 1
        }
      }
    }

    return distances;
  }

  function solution(n, edge) {
    // 그래프 생성
    let graph = [...Array(n + 1)].map(() => []);
    for (const [to, from] of edge) {
      graph[from].push(to);
      graph[to].push(from);
    }

    const distances = bfs(1, graph);
    const max = Math.max(...distances); // 거리 중 최대값

    return distances.filter((val) => val === max).length;
  }