[알고리즘] 배열의 fill 메서드 사용 시 주의!

문제

백준의 바이러스 문제를 풀 당시의 일이다.

너무 기본적인 실수를 해서 기록하기도 부끄럽지만 다음 번에 다시 반복하지 않기 위해 부끄러움을 감수하고 블로그에 적어본다,,

깊이 우선 탐색 유형의 문제를 풀 때, 인접하는 노드를 리스트 형태로 저장한 인접 리스트가 필요하다. 이 인접 리스트를 통해 재귀적으로 인접한 노드가 무엇인지 파악하고, 방문하지 않았다면 해당 노드를 방문해야 하기 때문이다.

따라서 graph라는 이름으로 인접 리스트를 하나 생성하는 코드를 작성했다.

다음의 두 코드를 비교해보자.

1번

let graph = [];
for (let i = 1; i <= n; i++) graph[i] = [];

for (let i = 2; i < links + 1; i++) {
  const [start, end] = input[i].split(" ").map(Number);

  graph[start].push(end);
  graph[end].push(start);
}

console.log(graph);

2번

const graph = new Array(n + 1).fill([]);

for (let i = 2; i < links + 1; i++) {
  const [start, end] = input[i].split(" ").map(Number);

  graph[start].push(end);
  graph[end].push(start);
}

console.log(graph);

input이 다음과 같다고 가정했을 때, graph의 결과는 어떻게 될까?

1 2
2 3
1 5
5 2
5 6
4 7

1번

[ [], [2, 5], [1, 3, 5], [2], [7], [1, 2, 6], [5], [4] ]

2번

[ [2, 1, 3, 2, 5, 1, 2, 5, 6, 5, 7, 4], [2, 1, 3, 2, 5, 1, 2, 5, 6, 5, 7, 4], [2, 1, 3, 2, 5, 1, 2, 5, 6, 5, 7, 4], [2, 1, 3, 2, 5, 1, 2, 5, 6, 5, 7, 4], [2, 1, 3, 2, 5, 1, 2, 5, 6, 5, 7, 4], [2, 1, 3, 2, 5, 1, 2, 5, 6, 5, 7, 4], [2, 1, 3, 2, 5, 1, 2, 5, 6, 5, 7, 4], [2, 1, 3, 2, 5, 1, 2, 5, 6, 5, 7, 4] ]

---

이유와 해결방법

왜 이런 일이 일어나게 되었을까?

문제는 이 코드에 있다.

const graph = new Array(n + 1).fill([]);

2번 코드는 fill([])을 사용하여 모든 graph의 요소에 같은 빈 배열 참조를 할당한다. fill 메서드는 배열의 모든 요소를 동일한 참조로 채우기 때문에, graph[1], graph[2] 등의 모든 요소가 같은 배열을 가리키게 되는 것이다.

따라서 graph[start].push(end)와 같은 작업을 수행하면 모든 graph[i]에 변경 사항이 동시에 반영된다.

이러한 상황을 방지하기 위해서는 1번과 같은 방법을 사용하거나, fill이 아닌 map을 이용해서 빈 배열을 graph에 저장하는 방법을 사용할 수 있을 것이다.

const graph = Array.from({ length: n + 1 }, () => []);

---

DFS 문제 풀이는 다 해 놓고 이런 실수를,,,

다시는 반복하지 않는 걸로 🫠