[Programmers LEVEL3] 가장 먼 노드 (ft. 스택오버플로우 첫 질문)

📗 문제 내용

[문제 링크]

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

[문제]

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

[제한 사항]

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

[입출력 예]

🧑🏼‍💻 나의 풀이

제한 사항을 보면 입력받은 edge 배열의 요소 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미이고, 간선은 양방향이라고 했다.

그래서 먼저 그래프를 2차원 배열로 만들어야겠다고 생각했고, 처음에 생각한 형태는 다음과 같다. 위 입출력 예시로 나타내보면,

const graph = [
  [ 1, 0, 0, 0, 0, 0 ],
  [ 0, 1, 0, 0, 0, 0 ],
  [ 0, 0, 1, 0, 0, 0 ],
  [ 0, 0, 0, 1, 0, 0 ],
  [ 0, 0, 0, 0, 1, 0 ],
  [ 0, 0, 0, 0, 0, 1 ]
];

먼저 graph를 초기화 하고, edge 배열을 토대로 1번 노드와 2번 노드가 연결되어 있다면 graph[1][2], graph[2][1]을 각각 1로 만들어주려고 했다.

하지만(!!) 제한 사항을 잘 보면 n의 범위는 2이상 20,000이하이다. 즉, 만약 입력으로 n이 20,000이 들어오게되면 FATAL ERROR: invalid array length Allocation failed - JavaScript heap out of memory 이런 에러를 만나게 된다. (11,000 정도만 들어와도 같은 에러가 발생한다.)

에러의 내용을 번역해보면 "배열에 길이 할당 실패, 자바스크립트 힙 메모리 초과"인데 그 이유가 궁금해졌다. 그래서 그냥 갑자기 스택오버플로우에 자바스크립트에서 배열에 최대로 할당 가능한 메모리 공간이 얼마인지에 대해 질문을 남기게 됐다.

정말 신기했던 건 질문을 남긴 지 5분도 채 되지 않았는데 아르메니아🇦🇲 개발자에게 댓글이 달렸다.

이스라엘🇮🇱 개발자에게는 이러한 답변을 받았다. 답변의 내용은 V8 JavaScript 엔진의 메모리 사용에는 제한이 있는데 64-bit 환경에서는 1GB라는 것이다. 그래서 node --max-old-space-size=4096 MyCode.js를 통해 그 메모리 사용 제한을 4GB로 늘릴 수 있다는 것이었다. 메모리 사용 제한을 늘리고 싶다는 의미는 아니었지만 궁금증이 해결됐다.

덕분에 알게된 사실을 덧붙이자면 자료형(Data Type)에서도 C언어는 컴퓨터 성능이 좋지 않은 시절에 개발된 언어라 작은 숫자는 적은 바이트를 차지하는 타입에 담고, 큰 숫자들은 많은 바이트를 차지하는 타입에 담아 컴퓨터 자원의 효율을 높혔지만 자바스크립트에서는, C언어가 처음 나온 시절에 비해 컴퓨터 성능이 많이 향상되어 1바이트든 8바이트든 크게 신경을 쓰지 않게 되었다고 한다.

문제 풀이로 다시 돌아와보면 그래프를 graph[출발 노드][도착노드] = 1 or 0; 형태로 만들 수 없으니 아래처럼 링크드 리스트의 모양으로 만들어야겠다고 생각했다.

const graph = [
  <1 empty item>,
  [ 3, 2 ],
  [ 3, 1, 4, 5 ],
  [ 6, 4, 2, 1 ],
  [ 3, 2 ],
  [ 2 ],
  [ 3 ]
];

즉 이러한 형태인데 1번 노드에는 2번과 3번 노드가 연결되어 있으므로 graph[1]에는 [ 3, 2 ]가 있다.

const graph = {
  '1': [ 3, 2 ],
  '2': [ 3, 1, 4, 5 ],
  '3': [ 6, 4, 2, 1 ],
  '4': [ 3, 2 ],
  '5': [ 2 ],
  '6': [ 3 ]
};

최종적으로는 graph를 시작 노드를 key로 하여 더 직관적인 객체로 구현했다. 코드는 배열로 구현했을 때와 거의 일치하고 실행시간도 비슷했다.

최종 코드

const solution = (n, edge) => {
  const graph = makeGraph(edge);

  const answer = Array(n + 1).fill(0), // 1번 노드로부터의 거리를 담을 배열
    check = Array(n + 1).fill(false); // 노드 방문 처리를 위한 배열
  const queue = [1]; // 시작 노드(1번)
  check[1] = true; // 1번은 방문했다고 하고 시작

  // BFS
  while (queue.length) {
    const current = queue.shift();

    graph[current].forEach(next => {
      if (check[next]) return; // 이미 방문했는지 check

      queue.push(next);
      check[next] = true;
      answer[next] = answer[current] + 1;
    });
  }

  let max = Math.max(...answer); // 최대 거리를 찾고
  return answer.filter(item => item === max).length; // 그 최댓값을 가지는 요소만 남긴 배열의 길이를 리턴
};

// 입력받은 edge 정보를 바탕으로 graph를 만들어 리턴하는 함수
const makeGraph = edge => {
  return edge.reduce((acc, cur) => {
    const [from, to] = cur;
    if (!acc[from]) acc[from] = [];
    if (!acc[to]) acc[to] = [];

    // 양방향 그래프이므로 양쪽 노드 모두 간선을 만들어준다.
    acc[from].push(to);
    acc[to].push(from);
    return acc;
  }, {}); // '{}'를 '[]'로 바꾸면 배열로도 구현이 가능하다.
};

console.log(
  solution(6, [
    [3, 6],
    [4, 3],
    [3, 2],
    [1, 3],
    [1, 2],
    [2, 4],
    [5, 2],
  ])
); // 3

매개변수 edge 배열을 통해 그래프를 만들고, BFS를 통해 answer 배열에는 1번 노드로부터의 거리를 1씩 증가하면서 담아주었고, check 배열로는 방문 처리를 해주었다. 두 배열 모두 0번 노드는 없고 1번 노드부터 시작하기 때문에 길이는 n+1로 설정했다. 마지막에는 answer 배열에 담긴 거리들 중 최댓값을 찾고, 그 값을 가진 요소만 남긴 배열로 필터링을 하여 그 배열의 길이를 최종 리턴했다.

리팩토링 전 코드

function solution(n, edge) {
  const graph = [];
  for (let i = 0; i < edge.length; i++) {
    if (!graph[edge[i][0]]) graph[edge[i][0]] = [];
    if (!graph[edge[i][1]]) graph[edge[i][1]] = [];
    graph[edge[i][0]].push(edge[i][1]);
    graph[edge[i][1]].push(edge[i][0]);
  }

  const check = Array(n + 1).fill(false),
    result = Array(n + 1).fill(0);
  const queue = [1];
  check[1] = true;

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

    if (!graph[current]) continue;
    for (let i = 0; i < graph[current].length; i++) {
      const next = graph[current][i];
      if (next === current || check[next]) continue;

      check[next] = true;
      queue.push(next);
      result[next] = result[current] + 1;
    }
  }

  let answer = 0;
  let max = Math.max(...result);
  for (const item of result) {
    if (max === item) answer += 1;
  }
  return answer;
}

Reference

• 자바스크립트로 프로그래밍 입문 5. 비트(Bit), 바이트(Byte) 그리고 자료형(Data Type)
• JavaScript 배열(Array)의 발전과 성능에 대해서 자세히 알아보기
• 자바스크립트에서 배열의 최대 크기