🔎 가장 먼 노드

❓ 문제링크

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

📄 제출 코드

let visited = [];
let depth = [];
function solution(n, edge) {
    visited = new Array(n + 1).fill(false);
    depth = new Array(n + 1);
    return bfs(edge, 1);
}
function bfs(edge, start) {
    let q = [start];
    depth[0] = 0;
    depth[start] = 0;
    visited[start] = true;
    let level;
    while (q.length != 0) {
        let node = q.shift();
        level = depth[node] + 1;
        edge.forEach(el => {
            if (el[0] == node && !visited[el[1]]) {
                q.push(el[1]);
                visited[el[1]] = true;
                depth[el[1]] = level
            } else if(el[1]==node && !visited[el[0]]){
                q.push(el[0]);
                visited[el[0]] = true;
                depth[el[0]] = level
            }
        })
    }
    return depth.filter((i) => i == level - 1).length;
}
let n = 6;
let edge = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]];
console.log(solution(n, edge));

처음에는 번호를 key로 갖는 객체를 만들고, edge를 돌면서 +1하면 풀릴거라 생각했는데 작성하다보니까 그렇게되면 그냥 그 노드에 몇개 연결됐는지만 알고, 깊이에 대해선 잘 모르게 된다.
그래서 고민을 하다가 질문게시판을 둘러보니 대부분 bfs로 푼 듯 했다.

시작은 1부터기 때문에 만들 때 길이는 n+1을 했다.
start길이만큼의 q를 만들고, 깊이의 start번째 값을 0, 방문체크를 해준다.
q를 돌때마다 level이 올라가게 되고, edge에서 연결된 두점을 가지고 조건을 나눈다.
edge[0]이 node고, edge[1]을 방문하지 않았다면, q를 다시 넣고 방문체크 후, el[1]의 레벨을 +1.
edge[1]이 node고, edge[0]을 방문하지 않았다면, q를 다시 넣고 방문체크 후, el[0]의 레벨을 +1.
이렇게 방문하지 않은거 까지 다 돌때까지 진행.

탐색 순서
level 1 : 1
level 2 : 3, 2
level 3 : 6, 4, 5

depth에는 0부터 저장이 되있으니 level-1한거를 depth에서 찾아 갯수를 리턴하면 답이됨.