[BFS] 가장 먼 노드

Problem. 가장 먼 노드

---

Link.

https://school.programmers.co.kr/learn/courses/30/lessons/49189

프로그래머스

---

Problem.

n개의 노드가 있는 그래프가 있습니다.

각 노드는 1부터 n까지 번호가 적혀있습니다.

1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다.

가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드를 의미합니다.

 

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때,

1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성하시오.

 

제한사항

1. 노드의 개수 n은 2 이상 20,000 이하 입니다

2. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다

3. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다

 

입출력 예시

// case#1
n = 6;
vertex = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]];
return = 3;

---

In Details.

Case#1

n = 6, vertex = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

 

Code#1. 각 노드의 간선 정보를 담을 배열

let graph = Array.from(Array(n + 1), () => []);

// -- description -- 

n = 6인 경우
Array.from(Array(7), () => []);
[[], [], [], [], [], [], []]

 

Code#2. 각 노드에 간선을 연결시킨다

for (let [head, rear] of edge) {
	graph[head].push(rear);
    graph[rear].push(head);
}

// -- description -- 

edge = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

Iteration #1
[3, 6] -> head = 3, rear = 6
graph[3].push(6)
graph[6].push(3)
[[], [], [], [6], [], [], [3]]

Iteration #2
[4, 3] -> head = 4, rear = 3
graph[4].push(3)
graph[3].push(4)
[[], [], [], [6, 4], [3], [], [3]]

Iteration #3
[3, 2] -> head = 3, rear = 2
graph[3].push(2)
graph[2].push(3)
[[], [], [3], [6, 4, 2], [3], [], [3]]

Iteration #4
[1, 3] -> head = 1, rear = 3
graph[1].push(3)
graph[3].push(1)
[[], [3], [3], [6, 4, 2, 1], [3], [], [3]]

Iteration #5
[1, 2] -> head = 1, rear = 2
graph[1].push(2)
graph[2].push(1)
[[], [3, 2], [3, 1], [6, 4, 2, 1], [3], [], [3]]

Iteration #6
[2, 4] -> head = 2, rear = 4
graph[2].push(4)
graph[4].push(2)
[[], [3, 2], [3, 1, 4], [6, 4, 2, 1], [3, 2], [], [3]]

Iteration #7
[5, 2] -> head = 5, rear = 2
graph[5].push(2)
graph[2].push(5)
[[], [3, 2], [3, 1, 4, 5], [6, 4, 2, 1], [3, 2], [2], [3]]

 

Code#3. 길이 정보를 세팅한 후, 노드 1의 길이를 1로 초기화

let length = Array(n + 1).fill(0);
length[1] = 1;

// -- description -- 

n = 6인 경우
Array(7).fill(0);
[0, 0, 0, 0, 0, 0, 0]
length[1] = 1;
[0, 1, 0, 0, 0, 0, 0]

 

Code#4. 큐에 1을 담고, 노드 1부터 순회

let queue[1] = 1;

while (queue.length > 0) {
	let src = queue.shift();
    for (let node of graph[src]) {
    	if (length[node] === 0) {
        	queue.push(node);
            length[node] = length[src] + 1;
        }
    }
}

// -- description --

 

Code#5. 최대 길이를 찾은 후, 최대 길이가 몇개 인지 반환

let max = Math.max(...length)
return length.filter((el) => el === max).length;

// -- description
max = 3;
length.filter((el) => el === max) => [3, 3, 3]
[3, 3, 3].length => 3

return 3;

---

My Answer. 

function solution(n, edge) {
    let graph = Array.from(Array(n + 1), () => []);
    // 그래프를 만들어준다
    // graph[1] = [2, 3]
    // graph[2] = [1, 4, 5]
    for (const [from, to] of edge) {
        graph[from].push(to);
        graph[to].push(from);
    }
    
    let distance = Array(n + 1).fill(0);
    distance[1] = 1;
    
    let queue = [1];
    
    while (queue.length > 0) {
        let src = queue.shift();
        
        for (const dest of graph[src]) {
            if (distance[dest] === 0) {
                queue.push(dest);
                distance[dest] = distance[src] + 1;
            }
        }
    }
    // 가장 먼 노드의 길이를 계산
    let max = Math.max(...distance);
    return distance.filter((el) => el === max).length;
}

---

References.

• 코딩테스트 광탈 방지 A to Z : JavaScript (이선협)
• Array.from() : https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/from

Array.from() - JavaScript | MDN

---

For Developer. 

• 잘못되거나 부족한 부분이 있다면 언제든지 댓글 부탁드립니다 :)