[JS] 가장 먼 노드

일단 이름부터 그냥 bfs 문제입니다.

다만 제한 사항이 있기 때문에 약간의 아이디어만 있다면 쉽게 푸실 수 있을거에요.

다들 푸셨나요? 혹시 8, 9 번이 시간 초과가 나진 않으신가요?

 

그렇다면 간단한 팁과 함께 같이 한번 보시죠!

---

문제 요약

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

 

제한사항

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

테스트케이스

n	vertex (edge)	return
6	[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]	3

1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다. 그러므로 3을 return!

접근 방법

전형적인 bfs이지만, 다음 노드를 찾을 때 루프안에서 edge를 조작하는 걸 조심해야합니다.

레벨 3 문제를 몇 개 안 풀어봤지만, 제한사항 등에서 디테일을 조심해야할 것 같아요.

노드의 갯수가 20,000개 이하이고 간선은 50,000개 이하이기 때문에 edge를 매번 filter해주는 과정이 최악의 경우 매번 50,000번의 루프를 태운다는 소리입니다.

 

bfs 루프 밖에서 다음 노드에 도착할 수 있는 해시맵이나 다중 배열을 미리 정의해두고 한번 이용해봅시다!아마 시간초과가 날 일은 없을 거에요.

 

동작 순서

1. 큐, 해시맵 등 필요한 클래스, 함수 제작
2. 노드 1에서 출발하여 bfs 시작
3. 길이 중 최댓값의 갯수를 return

 

정답 코드는 같이 보시죠! 약간 길지만 중요하게 봐야할 부분은 bfs 내부 정도..?

정답 코드

class Queue {
    constructor() {
        this.queue = [];
        this.front = 0;
        this.rear = 0;
    }
    
    enqueue(val) {
        this.queue[this.rear++] = val;
    }
    
    dequeue() {
        const val = this.queue[this.front];
        delete this.queue[this.front++];
        return val;
    }
    
    isEmpty() {
        return this.front === this.rear;
    }
    
    show() {
        return this.queue;
    }
}

function setNode(nodeMap, node1, node2) {
    if (nodeMap.has(node1)) {
        const arr = nodeMap.get(node1);
        arr.push(node2);
        nodeMap.set(node1, arr);
    } else {
        nodeMap.set(node1, [node2]);
    }
    return nodeMap;
}
function solution(n, edge) {
    const queue = new Queue();
    let nodeMap = new Map();
    for (const [node1, node2] of edge) {
        nodeMap = setNode(nodeMap, node1, node2);
        nodeMap = setNode(nodeMap, node2, node1);
    }
    nodeMap.get(1).forEach(v => queue.enqueue([1, v, 1]));
    const lengths = [0, 0, ...Array(n - 1).fill(Infinity)];
    
    while (!queue.isEmpty()) {
        const [prev, curr, length] = queue.dequeue();
        if (lengths[curr] > length) {
            lengths[curr] = length;
            const nextNodes = nodeMap.get(curr);
            nextNodes.forEach(v => queue.enqueue([curr, v, length + 1]));
        } else continue;
    }
    let max = Math.max(...lengths);
    return lengths.filter(v => v === max).length;
}

 

팁 1. Map은 왜 두 번씩 넣어주나요?

for (const [node1, node2] of edge) {
    nodeMap = setNode(nodeMap, node1, node2);
    nodeMap = setNode(nodeMap, node2, node1);
}

 

왜냐하면 양방향 간선이기 때문입니다. edge의 앞에 1이 오든, 뒤에 1이 오든 다음 노드의 대상입니다.

일단 전부 넣어놓은 다음 bfs 로직에서 걸러줍시다!

 

팁 2. bfs 동작 원리

while (!queue.isEmpty()) {
    const [prev, curr, length] = queue.dequeue();
    if (lengths[curr] > length) {
        lengths[curr] = length;
        const nextNodes = nodeMap.get(curr);
        nextNodes.forEach(v => queue.enqueue([curr, v, length + 1]));
    } else continue;
}

bfs 처음 다뤘던게 진짜 일주일정도 된거 같은데 꽤 많이 익숙해졌네요. 아니네요 2주일은 됐군요.

2022.07.19 - [알고리즘/programmers] - [JS] 게임맵 최단거리 - 미뤄뒀던 BFS에 대해

[JS] 게임맵 최단거리 - 미뤄뒀던 BFS에 대해

아무튼 중요한 건 visited(lengths)에 boolean을 쓰지 않고 1에서부터의 최소 거리를 넣어줬다는 점입니다.

이미 3다리만에 갈 수 있는 5를  4번, 5번에 가는 경우는 굳이 계산해 줄 필요가 없습니다.

그렇기 때문에 아무런 걱정 없이 위에서 정의한 nodeMap의 다음노드를 다 넣어줘도 됩니다.

만약 이전 노드로 돌아가거나 최소경로로 가지 않는다면 length가 더 커질 꺼기 때문에 자동으로 continue로 다음 노드로 넘어갈 수 있습니다.

 

레벨 3치곤 쉽네요. 한 0.5 조이스틱(이문제 왜 레벨 2임) 정도..?

그럼 이만!