[Javascript] 가장 먼 노드

목차

1. 문제 풀이

2. 정답 코드 (shift 연산 x)

3. 시간 복잡도 

---

1. 문제 풀이

1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하는 방법

- bfs 코드를 순회한다.

- visited 배열에 깊이(현재 노드까지의 간선의 개수)를 저장한다.

---

2. 정답 코드 (shift 연산 x)

shift() 연산을 O(1)로 만들기 위해 front 변수를 사용한다.

 

- 큐에서 노드 하나를 제거하기 위해

(1) q[front] 에서 노드를 꺼냄

(2) front++

이 두개의 연산(1 + 2)을 합쳐서

👉 var cur = q[front++]

 

- 언제까지 반복하는지

👉 while(front < q.length)

function solution(n, edge) {
    var answer = 0;

    var edges = Array.from({length: n + 1}, ()=> []);
    for (let i = 0; i < edge.length; i++) {
        edges[edge[i][0]].push(edge[i][1]);
        edges[edge[i][1]].push(edge[i][0]);
    }

    var q = [1];
    var visited = Array.from({length : n + 1}, ()=> -1);
    visited[1] = 0; 

    var front = 0; // 큐의 맨 앞을 가리킴

    while(front < q.length) {
        var cur = q[front++]; // 큐의 맨 앞 제거 및 인덱스 1 증가


        for (const next of edges[cur]) {
            if (visited[next] == -1) {
                visited[next] = visited[cur] + 1;
                q.push(next);
            }
        }
    }

    var maxDep = Math.max(...visited); 
    visited.forEach((v) => {if (v == maxDep) answer++ }); 

    return answer;
}

---

3. 시간 복잡도

✔ shift 연산을 사용하지 않았을 경우

모든 노드를 방문하는 수 : O(N)

연결된 간선을 방문하는 수 : O(E)

👉 O(N + E)

 

cf) shift 연산을 사용할 경우

shift 연산 : O(N) 이 추가되므로

👉 O(N^2 + E)