가장 먼 노드(DFS)

문제

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

프로그래머스

코드

function solution(n, edge) {
  const list = Array.from({ length: n + 1 }, () => []);
  edge.map(([x, y]) => {
    list[x].push(y);
    list[y].push(x);
  });

  const dis = [Infinity, 1];
  const queue = [1];

  while (queue.length) {
    const cur = queue.shift();

    for (let next of list[cur]) {
      if (!dis[next]) {
        dis[next] = dis[cur] + 1;
        queue.push(next);
      }
    }
  }

  dis.shift();
  let count = 0;
  const max = Math.max(...dis);
  dis.map((len) => {
    if (len === max) count++;
  });

  return count;
}

풀이 방법

이 문제는 DFS를 이용해서 푸는 방법이다. 처음에는 플로이드 알고리즘을 이용해서 풀었지만 예시만 맞고 틀렸다.

 

  const list = Array.from({ length: n + 1 }, () => []);
  edge.map(([x, y]) => {
    list[x].push(y);
    list[y].push(x);
  });

list에 서로 연결되어 있는 노드를 정의해준다.

 

  const dis = [Infinity, 1];
  const queue = [1];

dis는 각 노드를 방문하는데 걸린 횟수를 저장한다. 맨 처음이 Infinity인 이유는 노드 번호가 1번부터 시작이라 이를 고려하기 위해서 임의로 넣어줬다.

queue에 노드들을 넣고 맨 앞 노드부터 방문하기 위한 리스트이다.

 

  while (queue.length) {
    const cur = queue.shift();

    for (let next of list[cur]) {
      if (!dis[next]) {
        dis[next] = dis[cur] + 1;
        queue.push(next);
      }
    }
  }

반복문을 queue가 있을 때 까지 반복한다. cur은 현재 방문 중인 노드 번호를 의미한다. 

for문에서 현재 노드와 연결된 노드를 방문한다. dis에 현재 노드와 연결된 노드가 없으면 현재 노드의 방문 횟수에서 +1해서 넣어주고 queue에 다음번에 방문할 노드를 넣어준다.

 

  dis.shift();
  let count = 0;
  const max = Math.max(...dis);
  dis.map((len) => {
    if (len === max) count++;
  });

  return count;

dis.shift()를 하여 임시로 있던 Infinity를 제거해준다. 그리고 dis에서 가장 큰 숫자를 얻고 dis 안에 가장 큰 숫자 개수를 계산해 리턴해주면 된다.