[JS] 프로그래머스 Lv3 가장 먼 노드

문제 링크

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

첫 트라이

1. 양방향 그래프를 만들기
2. dfs로 edge를 순회
3. 거리 계산

let graph = {}, dist;

const dfs = (target, dp = 1) => {
    graph[target].filter(e => !dist[e] || dist[e] > dp).forEach(e => {
        dist[e] = dp;
        dfs(e, dp + 1)
    })
}

function solution(n, edge) {
    edge.forEach(([a, b]) => {
        graph[a] = graph[a] ? [...graph[a], b] : [b];
        graph[b] = graph[b] ? [...graph[b], a] : [a];
    })
    dist = {1: -1};
    dfs(1);
    const distArr = Object.values(dist);
    const max = distArr.reduce((ac, v) => ac > v ? ac : v, 0)
    return distArr.filter(e => e === max).length;
}

하지만 런타임 에러 발생... 너무 깊어져서 그런가..

두번째 트라이

bfs를 통해서 탐색
방문 배열을 따로 만들지 않고 거리배열로 탐색하기에
거리가 0인 노드, e !== 1이 부분을 주의해야 한다.

function solution(n, edge) {
    const graph = {}, dist = {1: 0};
    edge.forEach(([a, b]) => {
        graph[a] = graph[a] ? [...graph[a], b] : [b];
        graph[b] = graph[b] ? [...graph[b], a] : [a];
    })

    const q = [1];
    while (q.length) {
        const cur = q.shift();
        const nextDist = dist[cur] + 1;
        graph[cur].filter(e => e !== 1 && (!dist[e] || dist[e] > nextDist)).forEach(e => {
            dist[e] = nextDist;
            q.push(e);
        })
    }
    const distArr = Object.values(dist);
    const max = distArr.reduce((ac, v) => ac > v ? ac : v, 0)
    return distArr.filter(e => e === max).length;
}

✨ 최종 코드 (코드 최적화)

1. bfs 특성상 첫 방문할 때가 가장 거리가 짧다
2. 마지막 방문한 노드의 거리가 제일 먼 거리이다

function solution(n, edge) {
    const graph = {}, dist = { 1: 0 };
    edge.forEach(([a, b]) => {
        graph[a] = graph[a] ? [...graph[a], b] : [b];
        graph[b] = graph[b] ? [...graph[b], a] : [a];
    })

    const q = [1];
    let nextDist;
    while (q.length) {
        const cur = q.shift();
        nextDist = dist[cur] + 1;
        graph[cur].filter(e => e !== 1 && !dist[e]).forEach(e => {
            dist[e] = nextDist;
            q.push(e);
        })
    }
    return Object.values(dist).filter(e => e === nextDist-1).length;
}

그래프를 만들지 않고 순회한 경우

테스트 캐이스는 통과 되더라 ㅋㅋㅋ

function solution(n, edge) {
    const visit = {1: 1};
    const dp = {1: 0};
    const q = [1];
    let deep;
    while (q.length) {
        const cur = q.shift();
        deep = dp[cur];
        const nexts = [].concat(...edge.filter(e => e.find(node => node === cur)));
        nexts.filter(nt => !visit[nt]).forEach(nt => {
            visit[nt] = 1;
            dp[nt] = deep + 1;
            q.push(nt);
        });
    }
    return Object.values(dp).filter(e => e === deep).length;
}