(프로그래머스 JS)가장 먼 노드

https://programmers.co.kr/learn/courses/30/lessons/49189?language=javascript 

코딩테스트 연습 - 가장 먼 노드

큐와 BFS를 이용한 문제 풀이.

 

우선 그래프를 그리기 위해 n + 1의 크기만큼 2차원 배열 graph를 선언.

노드의 방문 여부를 알기 위한 visited 배열을 선언.

 

for문.

주어진 edge는 무방향 그래프이기 때문에 두 노드에 해당하는 번호를 각각 넣어줘야 한다.

 

큐 class를 만들어 bfs를 위한 큐를 만든다.

문제가 1부터 가장 먼 노드를 찾아야 하기 때문에 큐에 1을 넣어 시작(visited[1]도 true로 바꾼다.)

 

BFS.

현재 큐에 담겨있는 사이즈가 answer가 될 수 있다.

왜냐하면 가장 끝까지 간 경우, 큐가 비기 때문에 현재 depth의 노드 개수가 큐의 현재 크기이기 때문이다.

 

큐의 size만큼 while문 실행.

현재 방문한 노드의 인접한 노드 중 방문하지 않은 노드는 큐에 넣어준다.

visited 또한 true로 설정.

(size만큼 실행하기 때문에 새로 추가된 노드는 다음 depth에서 방문한다.)

 

이 while문을 실행하면 자동으로 1에서 가장 먼 노드들의 개수를 구할 수 있다.

class Queue{
    constructor(){
        this.queue = [];
        this.front = 0;
        this.rear = 0;
    }
    
    push(value){
        this.queue[this.rear++] = value;
    }
    
    pop(){
        const value = this.queue[this.front];
        delete this.queue[this.front++];
        
        return value;
    }
    
    size(){
        return this.rear - this.front;
    }
}

function solution(n, edge) {
    let answer = 0;
    const queue = new Queue();
    const graph = Array.from(Array(n + 1), () => []);
    const visited = Array.from(Array(n + 1).fill(false));
    
    for(const v of edge){
        const e1 = v[0];
        const e2 = v[1];
        
        graph[e1].push(e2);
        graph[e2].push(e1);
    }
    
    queue.push(1);
    visited[1] = true;
    
    while(queue.size()){
        let size = queue.size();
        answer = size;
        
        while(size--){
            const start = queue.pop();
            
            for(let i = 0; i < graph[start].length; i++){
                const target = graph[start][i];
                
                if(!visited[target]){
                    queue.push(target);
                    visited[target] = true;
                }
            }
        }
    }
    
    return answer;
}