[JS/Programmers] 49189. 가장 먼 노드

💬 문제

문제 난이도: Programmers Lv.3

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/49189

❗️접근방법

그래프, bfs, queue

👆 1차 코드(통과❌)

function solution(n, edge) {
    const visited = new Array(n).fill(n);
    visited[0] = 0;
    for (let i = 0; i < edge.length; i+=1){
        const [node1, node2] = edge[i];
        if (node1 > node2) edge[i] = [node2, node1];
    }
    edge.sort((a, b)=> a[0]-b[0]);
    // console.log(edge);
    for (let i = 0; i < edge.length; i+=1){
        const [node1, node2] = edge[i];
        if (node1 === 1){
            visited[node2-1] = 1;
        }else{
            visited[node2-1] = Math.min(visited[node2-1], visited[node1-1] + 1)
        }
    }
    const longest = Math.max(...visited);
    // console.log(visited)
    return visited.filter(elem => elem === longest).length;
}

반례: [[1, 4], [1, 5], [2, 3], [3, 4]]
인접한 노드도 오름차순으로, 간선들도 오름차순으로 정렬한다고 할지라도 위의 반례에 대해서는 의도한 바대로 처리할 수 없다.
2번과 3번 노드는 1번 노드와 인접해 있지 않고, 3번 노드가 [2, 3] 간선 뒤에 오는 [3, 4]에 의해 간접적으로 1번 노드와 연결되기 때문에
위와 같은 방식으로 정렬하는 방식은 문제의 의도와 맞지 않다.

✌️ 2차 코드(통과✅)

class Queue {
	constructor(){
		this.storage = {};
		this.front = 0;
		this.rear = 0;
	}

	size() {
		if (this.storage[this.rear] === undefined) return 0;
		else return this.rear - this.front + 1;
	}

	add(value) {
		if (this.size() === 0){
			this.storage['0'] = value;
		} else {
			this.rear += 1;
			this.storage[this.rear] = value;
		}
	}
		
	popleft() {
		let temp;
		if(this.size() === 0) temp = undefined;
		else if (this.front === this.rear) {
			temp = this.storage[this.front];
			delete this.storage[this.front];
			this.front = 0;
			this.rear = 0;
		} else{
			temp = this.storage[this.front];
			delete this.storage[this.front];
			this.front += 1;
		}
		return temp;
	}
}

function bfs(distance, queue, obj){
    let longest = 0;
    while(queue.size() > 0){
        const start = queue.popleft();
        for (let i = 0; i < obj[start].length; i+=1){
            const next = obj[start][i]; // 2
            if (distance[next] === -1) {
                distance[next] = distance[start]+1;
                queue.add(next);
                longest = Math.max(longest, distance[next]);
            }
        }
    }
    return longest;
        
}

function solution(n, edge) {
    const obj = {};
    for (let i = 0; i < edge.length; i+=1){
        const [node1, node2] = edge[i];
        if (obj.hasOwnProperty(node1)) obj[node1].push(node2);
        else obj[node1] = [node2];

        if (obj.hasOwnProperty(node2)) obj[node2].push(node1);
        else obj[node2] = [node1];
    }
    
    const distance = new Array(n+1).fill(-1);
    distance[1] = 0;
    const queue = new Queue();
    queue.add(1);
    const longest = bfs(distance, queue, obj);
    return distance.filter(elem=>elem === longest).length;
}

1. 양방향 그래프임을 감안해 각 노드를 key로, 그 노드와 인접한 노드를 배열의 원소로 갖는 value로 갖는 객체(obj)를 만든다.
2. 방문 여부와 1번 노드로부터 최단 거리를 기록하기 위한 distance 배열을 만든다. 방문하지 않음을 의미하는 -1로 모든 원소를 초기화한다.
3. 1번 노드에서부터의 최단거리를 구해야 하므로 bfs를 사용해 탐색한다.
4. bfs 함수 내의 longest 변수를 통해 1번 노드로부터 가장 먼 노드까지의 거리를 알아낸다.
5. bfs 탐색이 끝난 후에 distance 배열에서 longest 값과 같은 원소의 개수를 구한다.