그래프 문제를 풀다가 어이 없었던 실수_배열 객체에 대한 고찰

문제

https://github.com/choi2601/LeetCode-ProblemSolving/tree/main/797-all-paths-from-source-to-target

GitHub - choi2601/LeetCode-ProblemSolving: 👨🏼‍💻 LeetCode 알고리즘 문제풀이 코드 저장소

릿코드에서 인접 행렬 그래프 문제를 풀다가 어이 없는 실수로 인해 오랜 시간 고민을 했다.

다시는 같은 실수를 하지 않기 위해 해당 부분을 짧게 포스팅하고자 한다.

 

배열 객체

const answer = [];
    const n = graph.length;
    const nodes = Array.from(Array(n), () => Array());
    const ch = Array.from({length: n}, () => 0);
    
    for(let i = 0; i < graph.length; i++) {
        const route = graph[i];
        for(let j = 0; j < route.length; j++) {
            const path = route[j];
            nodes[i].push(path);
        }
    }
    
    const tmp = [0];
    
    function DFS(v) {
        if(v === n - 1) {
            answer.push(tmp);
            return;
        }
        else {
            for(let i = 0; i < nodes[v].length; i++) {
                if(ch[nodes[v][i]] === 0) {
                    ch[nodes[v][i]] = 1;
                    tmp.push(nodes[v][i]);
                    DFS(nodes[v][i]);
                    ch[nodes[v][i]] = 0;
                    tmp.pop();
                }
            }
        }
    }
    
    ch[0] = 1;
    DFS(0);
    
    return answer;

해당 코드는 처음에 작성한 코드로서, 다음과 같이 계속 정답이 틀리게 나왔다.

[[0],[0]]

지나온 경로를 임시 저장하는 변수인 tmp를 콘솔창에 찍어봤을 때는 올바른 경로 행적이 나오는데, 경로가 담긴 정답 변수를 반환하면 위와 같이 초기 경로인 0만을 담은 배열이 나왔다.

 

오랜 시간 고민을 해본 결과, 배열이 객체 라는 사실을 기억해 냈다.

 

배열은 객체로서, 참조값에 의해 값(value)가 공유되기 때문에, 다시 경로를 되돌아왔을 때 이전 행적을 없애기 위한 tmp.pop() 연산이 최종 결과에 영향을 미친 것 이었다.

 

이에 원본 배열을 정답 변수에 바로 push()하는 것이 아닌, Array.prototype.slice()를 사용하여 원본 배열을 깊은 복사한 새로운 참조값을 지닌 배열 객체를 정답 변수에 push() 해줌으로써 문제를 해결할 수 있었다.