[CodeKata] 프로그래머스 : 5.4(화), 가장 먼 노드

🥋 Oooth More!! (Level 3)

 

🧮 풀이

* 7, 8, 9번에서 메모리 초과 오류가 발생하였다.

function solution(n, edge) {
  const vertex = Array.from({ length: n }, () => new Array(n).fill(false));
  edge.forEach(e => vertex[e[0]-1][e[1]-1] = vertex[e[1]-1][e[0]-1] = true);

  let check = new Array(n).fill(0);
  let queue = [0];
  
  while (queue.length > 0) {
    const node = queue.shift();
    vertex[node].forEach((path, idx) => {
      if (path && check[idx] === 0) {
        check[idx] = check[node] + 1;
        queue.push(idx)
      }
    })
  }
  
  return check.slice(1).filter(v => v === Math.max(...check)).length;
}

1. 우선, vertex라는 2차원 배열 체크리스트를 만든 뒤, edge의 각 값을 통해 이동가능 경로(양방향)만 true 처리를 했다.
2. check 배열은 각 노드까지의 최단경로를 저장한다 (0은 방문x). queue는 현재 방문중인 노드를 꺼내고, 인접노드를 다시 넣는다.
3. while 반복문을 queue가 빌 때까지 실행한다. (비었다면, 더 이상 방문하지 않은 인접노드가 없다는 의미)
4. node는 queue 맨 앞에서 꺼낸 노드(인덱스 값)이다. vertex[node] 를 순회하며, 경로가 true고 check가 0인 인덱스를 찾는다.
5. 이 인덱스(idx)에 대해, check[idx]는 check[node] 현재 노드까지 최단경로에 1을 더한 값이며, queue에 idx를 넣어준다.
6. 마지막으로, check의 최대값의 갯수를 반환한다. 0번째(1번 노드)는 무조건 2가 저장되므로 이를 slice() 한다.(인접노드 왕복경로)

 

🖇 리뷰

const solution = (n, edge) => {
    const graph = Array.from({ length: n }, () => [])
    edge.forEach(([a,b]) => {
        graph[a-1].push(b-1)
        graph[b-1].push(a-1)
    })

    const q = [[0,0]]
    const visited = [true]
    const depNum = []
    while (q.length) {
        const [cur, dep] = q.shift()
        depNum[dep] = depNum[dep] ? depNum[dep]+1 : 1
        graph[cur].forEach(n => {
            if (!visited[n]) {
                visited[n] = true
                q.push([n, dep+1])
            }
        })
    }

    return depNum[depNum.length-1]
}

우선, graph가 내가 만든 vertex 체크배열과 유사하다. 다만, 2차원 배열이 아닌 각 인덱스에서 갈 수 있는 노드만 배열형태로 저장했다.

또, 큐에 [노드, 경로길이] 튜플 형태로 저장하며, depNum의 각 인덱스(경로길이)에 해당하는 노드 개수를 누적하는 형태이다.

 

n의 제곱수만큼 증가하는 2차원 배열에 비해, edge의 2배만 저장되는 차이에서 메모리 효율성이 급증하지 않았난 추정한다.

또한, 큐는 튜플이고 경로길이는 visited와 별도 배열에서 관리하였는데, 이 방법이 오히려 메모리를 효율적으로 사용한 게 신기했다.