서문

이 문제는 그래프 문제로 1번 노드에서 가장 멀리 있는 노드들의 개수를 구하는 문제이다. 그래프 문제를 풀기 전에 DFS/BFS 문제를 좀 풀었더니 해결하는 데에 도움이 많이 된 것 같다.

소스 코드

function solution(n, edge) {
  let answer = 0;
  const visited = new Array(n + 1); // 노드 방문 체크 배열
  const distances = new Array(n + 1).fill(0); // 노드까지의 최단거리를 저장할 배열
  const predecessors = new Array(n + 1).fill(0); // 해당 노드의 전 노드를 저장할 배열
  const queue = [1]; // BFS를 위한 큐
  const adjList = new Array(n + 1); // 인접 리스트

  // 인접리스트 구성
  for (let i = 1; i <= n; i++) {
    adjList[i] = new Array();
  }
  for (let i = 0; i < edge.length; i++) {
    if (!adjList[edge[i][0]].includes(edge[i][1]))
      adjList[edge[i][0]].push(edge[i][1]);
    if (!adjList[edge[i][1]].includes(edge[i][0]))
      adjList[edge[i][1]].push(edge[i][0]);
  }

  visited[1] = true;
  while (queue.length !== 0) {
    const curNode = queue.shift();

    adjList[curNode].forEach(item => {
      if (!visited[item]) {
        visited[item] = true;
        distances[item] = distances[curNode] + 1;
        predecessors[item] = curNode;
        queue.push(item);
      }
    });
  }

  let max = 0;
  distances.forEach(item => {
    if (max < item) {
      max = item;
      answer = 1;
    } else if (max === item) {
      answer++;
    }
  });

  return answer;
}

문제 풀이

먼저 이 문제는 BFS를 활용하여 해결하였다. 그래서 어떤 노드를 방문했는지 기억하기 위해 visited배열을 활용하여 체크해주었다. 또, 각 노드까지의 최소 거리를 구하기 위해서 distances배열을 선언하여 저장해주었다. predecessors 배열은 각 노드로 건너온 전 노드를 가리키는데 이는 학습 목적으로 선언해본 것이다. queue는 BFS 구현을 위해 선언해주었고, adjList는 인접 리스트를 구현하기 위해 선언했다.

먼저 인접리스트부터 구성을 했다. 각 노드에 해당하는 index에 연결되어 있는 다른 노드들의 index를 저장했다. 인접 행렬을 사용할 수도 있는데, 본 문제처럼 n이 클 경우에는 순회하는데 오랜 시간이 걸릴 수 있다.

그 후 가장 처음으로 방문할 노드인 1번 노드를 큐에다 넣어준다. 그리고 1번 노드는 시작과 동시에 방문했으므로

visited[1] = true;

위와 같이 처리해준다.

이제 큐가 빌 때까지 반복문을 돌면서 큐에서 하나씩 데이터를 꺼낸다. 꺼낸 데이터를 토대로 인접 리스트를 순회하면서 나오는 모든 데이터를 큐에다가 넣어준다. 여기서 큐에 데이터를 넣어줄 때, 방문 체크를 해주어야 한다. 처음에 잘못 구현했을 때에는 데이터를 꺼낼 때 방문체크를 해주었는데, 이러면 거리 계산이 꼬이게 되는 경우가 생긴다.

예를 들어보겠다. 1번 노드에서 2번 노드로 접근 할 수 있어서 2번 노드를 큐에 넣어주었다. 물론 2번 노드에 대해서 방문 체크는 해주지 않았다. 그 후, 3번 노드에서 2번 노드에 접근할 수 있어서 2번 노드를 다시 큐에 넣어주었다. 이렇게 되면 2번 노드가 큐에 두 번 들어가게 되었다. 그러면 1 -> 2 의 경우와 1 -> 3 -> 2 의 경우가 되는건데 이는 최소 거리가 아니므로 틀린 경우다.

즉 데이터를 큐에서 꺼낼 때 방문 체크를 해주는 것이 아니라, 데이터를 큐에 넣는 순간에 방문 체크를 해주어야 이런 오류를 피할 수가 있다.

adjList[curNode].forEach(item => {
  if (!visited[item]) {
    visited[item] = true;
    distances[item] = distances[curNode] + 1;
    predecessors[item] = curNode;
    queue.push(item);
  }
});

위의 코드에서 방문 처리 외에 거리 계산을 해주는 코드도 있다.

distances[item] = distances[curNode] + 1;

위의 부분인데, 현재 방문중인 노드의 거리에서 1을 더해준 값이 큐에 넣어줄 노드까지의 거리가 된다.

밑의

predecessors[item] = curNode;

부분은 전 노드의 값을 저장해주는 과정이다. 그 후 데이터를 큐에 넣어준다.

이렇게 BFS로 순회를 다 해주면, distances배열에 각 노드까지의 최소 거리가 저장이 된다.

문제는 이 중에서 가장 먼 노드들의 개수를 구하라고 하였으므로 나는 아래와 같이 코드로 구현하였다.

  let max = 0;
  distances.forEach(item => {
    if (max < item) {
      max = item;
      answer = 1;
    } else if (max === item) {
      answer++;
    }
  });

가장 먼 거리를 구하기 위해 max 변수를 사용했다. distances 배열을 순회하면서 각 요소에 대해 최댓값인지 검사를 해준다. 그 후 최댓값이면 max를 업데이트해주고, answer의 값을 1로 초기화해준다.

만약 max의 값과 각 요소의 값이 같으면 가장 먼 거리에 해당하는 노드이므로 answer의 값을 1 증가시켜준다.

최종적으로 answer를 반환하면 이 문제의 정답이된다.

후기

처음 이 문제를 풀 때, 습관적으로 DFS로 접근하여 풀었다. 결과는 좋지 않았다. 기본 테스트 케이스는 정답이었지만 실제 코드를 제출하면 시간 초과가 뜨는 경우도 있고 런타임 에러가 나는 경우도 있었다.

그래서 BFS로 다시 도전을 해보았다. BFS가 익숙치 않아서 푸는 데에 꽤 오랜 시간을 쓰고 말았다. 어찌어찌 풀게 되었는데 솔직하게 말해서 코드가 깔끔하지 못했다.

그래서 구글에서 BFS 알고리즘 설명에 관해 검색을 해보고 공부를 하고 다시 풀어보았다. 훨씬 코드가 깔끔해질 수 있었고, 불필요한 부분을 줄일 수 있었다.

많은 공부가 된 문제였고, 앞으로 BFS로 문제 푸는것이 훨씬 수월해질 것 같다.