프로그래머스 가장 먼 노드 실습 중 에러

부트캠프 과제를 실행하던 중 BFS 알고리즘으로 가장 먼 노드 실습을 진행하고 있었다.

 

문제는 다음과 같다

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

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

제한사항

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

나는 각 노드의 연결을 matrix로 구현을 했었다.

코드는 다음과 같다.

class Queue {
    constructor(){
        this.queue = [];
        this.start = 0;
        this.end = this.queue.length;
    }
    
    enqueue(data) {
        this.queue.push(data);
        this.end += 1;
    }
    
    dequeue() {
        const returnData = this.queue[this.start];
        this.queue[this.start] = null;
        this.start += 1;
        return returnData;
    }
    
    queueSize() {
        return this.end - this.start;
    }
}

class Graph {
    constructor(n,graph) {
        this.graph = this.makeGraph(n, graph);
        this.visited = new Array(n+1).fill(0);
        this.visited[0] = null;
        this.depth = 1;
        this.queue = new Queue();
    }
    
    makeGraph(n, graph) {
        const newGraph = Array.from(Array(n+1), () => Array(n+1).fill(null))
        for(let i of graph) {
            newGraph[i[0]][i[1]] = 1;
            newGraph[i[1]][i[0]] = 1;
        }
        return newGraph;
    }
    
    bfs(node) {
        this.queue.enqueue(node);
        this.visited[node] = this.depth;
        while(this.queue.queueSize()) {
            const firstData = this.queue.dequeue();
            this.depth = this.visited[firstData]+1;
            this.graph[firstData].map((value,index) => {
                if(value == 1 && this.visited[index]==0) {
                    this.queue.enqueue(index);
                    this.visited[index] = this.depth;
                }
            })
        }
    }
}

function solution(n, edge) {
    const graph = new Graph(n, edge);
    graph.bfs(1);
    const maxNode = Math.max(...graph.visited);
    return graph.visited.filter((value) => value === maxNode).length; 
}

 

하지만 이런 코어 에러가 나는 것이다!

그래서 알아보니 adjacent matrix는 노드 개수의 제곱만큼의 메모리를 먹고 adjacent list는 엣지 개수 만큼의 메모리를 먹어 다음과 같이 오류가 나는 것이었다..! 그래서 adjacent list 방식으로 바꾸어 주었더니 에러가 해결되었다.

 ( 인터넷에 떠도는 방식보다 더 빨리 실행돼서 기분이 좋다 
 이유는 queue 방식에서는 배열 맨 앞을 빼내는 shift함수를 사용하면 안되기 때문에 나는 직접 queue를 구현해 주었다. )

 

바뀐 코드

class Queue {
    constructor(){
        this.queue = [];
        this.start = 0;
        this.end = this.queue.length;
    }
    
    enqueue(data) {
        this.queue.push(data);
        this.end += 1;
    }
    
    dequeue() {
        const returnData = this.queue[this.start];
        this.queue[this.start] = null;
        this.start += 1;
        return returnData;
    }
    
    queueSize() {
        return this.end - this.start;
    }
}

class Graph {
    constructor(n,graph) {
        this.graph = this.makeGraph(n, graph);
        this.visited = new Array(n+1).fill(0);
        this.visited[0] = null;
        this.depth = 1;
        this.queue = new Queue();
    }
    
    makeGraph(n, graph) {
        const newGraph = new Array(n+1).fill(0).map(e => []);
        for(let i of graph) {
            newGraph[i[0]].push(i[1]);
            newGraph[i[1]].push(i[0]);
        }
        return newGraph;
    }
    
    bfs(node) {
        this.queue.enqueue(node);
        this.visited[node] = this.depth;
        while(this.queue.queueSize()) {
            const firstData = this.queue.dequeue();
            this.depth = this.visited[firstData]+1;
            this.graph[firstData].map((value,index) => {
                if(this.visited[value]==0) {
                    this.queue.enqueue(value);
                    this.visited[value] = this.depth;
                }
            })
        }
    }
}

function solution(n, edge) {
    const graph = new Graph(n, edge);
    graph.bfs(1);
    const maxNode = Math.max(...graph.visited);
    return graph.visited.filter((value) => value === maxNode).length; 
}