[프로그래머스] 그래프/BFS - 가장 먼 노드 문제풀이 (Javascript)

위 문제 설명에 노드와 간선으로 보고 그래프 문제인 것을 알 수 있다. 

핵심 키워드는 "노드", "간선", "최단 경로"

최단 경로가 제일 큰 경우의 집합의 수를 구하는 문제이다

[자료구조] 그래프 
노드와 간선으로 이루어진 자료구조 

문제 풀이는 노드의 너비를 탐색하여 푸는 문제이기 때문에 BFS 풀이 방식 Queue를 이용해서 풀 수 있다.

Queue 를 풀 때 간단하게 Array 형식으로 만들어 Shift를 사용하여 만들 수 있지만 많은 데이터를 테스트 케이스로 이용할 때 시간이 오래 걸린다는 단점이 있다. 

따라서 Queue 클래스를 만들어 dequeue방식을 사용하자. 

Queue 클래스는 구현하기 간단하기 때문에 생각해서 자주 사용하는 것이 좋다. 

    const graph = Array.from(Array(n + 1), () => []) //노드가 1부터 시작하므로 n+1을 해준다 

    for (const [src, dest] of edge) {
        graph[src].push(dest)
        graph[dest].push(src)
    } //양방향이므로 양쪽에다가 넣어줌
    
    const distance = Array(n + 1).fill(0)

그래프를 만들 때 먼저 빈 array형태로 넣어준다. 그리고 노드에 값을 빈 Array에 넣어두고, 양방향이므로 양쪽에 넣어둔다.

 

전체 풀이 

//방법 1
//queue array 를 만들어 shift사용
function solution(n, edge) {
    const graph = Array.from(Array(n + 1), () => []) //노드가 1부터 시작하므로 n+1을 해준다 

    for (const [src, dest] of edge) {
        graph[src].push(dest)
        graph[dest].push(src)
    } //양방향이므로 양쪽에다가 넣어줌
    
    const distance = Array(n + 1).fill(0)
    distance[1] = 1;
    
    const queue = [1]
    while (queue.length > 0) {
        const src = queue.shift();
        ///거리구하는 원리
        for (const dest of graph[src]) {
            if (distance[dest] === 0) {
                distance[dest] = distance[src] + 1; //출발지의 1을 더해준다 
                queue.push(dest)
            }
        }
    }
    console.log(distance)
    return distance.filter(x => x === Math.max(...distance)).length
}
//방법 2
//queue class 를 만들어 shift을 사용하지 않고 구하는 함수
class Queue{
    constructor(){
        this.queue = [];
        this.head = 0;
        this.tail = 0;
    }
    enqueue(value){
        this.queue[this.tail++] = value;
    }
    dequeue(){
        const value = this.queue[this.head];
        delete this.queue[this.head]; //값은 empty로 되지만 head값을 증가하여 없앤 것처럼 보임
        this.head += 1;
        return value
    }
    isEmpty(){
        return this.head === this.tail;
    }
}
function solution(n, edge) {
    const graph = Array.from(Array(n + 1), () => []) 
    for (const [src, dest] of edge) {
        graph[src].push(dest)
        graph[dest].push(src)
    } 
    
    const distance = Array(n + 1).fill(0)
    distance[1] = 1;
    
    // BFS
    const queue = new Queue;
    queue.enqueue(1);
    
    while (!queue.isEmpty()) {
        const src = queue.dequeue();
        ///거리구하는 원리
        for (const dest of graph[src]) {
            if (distance[dest] === 0) {
                distance[dest] = distance[src] + 1; //출발지의 1을 더해준다 
                queue.enqueue(dest)
            }
        }
    }
    return distance.filter(x => x === Math.max(...distance)).length
}