[Level3][Javascript]가장 먼 노드

1. NxN adjacent Matrix로 풀게되면 66점이며, coredump error가 발생한다. // (signal: aborted (core dumped))

추후에 signal: segmentation fault (core dumped) 과 비교해보는 걸 작성할 필요가 있을 것 같다. 

function solution(n, edge) {
    let adjacent=[]
    for (let i=0; i<n;i++){
        adjacent.push(new Array(n+1).fill(0));
    }
    for(let i=0; i<n;i++){
        adjacent[i][i]=1;
    }
    // console.log(adjacent);
    
    edge.forEach(e=>{
        adjacent[e[0]-1][e[1]-1]=1;
        adjacent[e[1]-1][e[0]-1]=1;
    })
    // console.log(adjacent);
    
    let answer= bfs(adjacent,n);
    return answer;
}

function bfs(adjacent,n){
    let visited=new Array(n).fill(0);
    let Q=[];
    let ans=0;
    visited[0]=1;// 2 is fully visited, 1 is booked to be visited
    Q.push(0);
    while(Q.length!==0){
        let a= Q.shift();
        for(let i=0; i<n;i++){
            if(adjacent[a][i]==1 && visited[i]==0) {
                Q.push(i);
                visited[i]=visited[a]+1;
            }
        }
    }
    console.log(visited);
    max= Math.max.apply(null, visited);
    // console.log(max);
    for(let i=0; i<n;i++){
        if(visited[i]==max) {ans+=1;}
    }
    return ans;
}

2. Adjacency List 로 풀 필요가 있다... 

a) 검색해서 찾은 풀이인데, Array.from으로 [ [], [] , [], [], [],.. ] 구현해주는게 우선 인상적이다. 

const[src,dest] of edge도 상당히 인상적이다. 다만 변수명을 graph가 아닌 adjacencyList정도로 표현하는게 좋아보인다.

근데 이게 graph가 const여도 돌아가는 이유가 뭐지..?

//https://github.com/codeisneverodd/programmers-coding-test
//완벽한 정답이 아닙니다.
//정답 1 - codeisneverodd
function solution(n, edge) {
    const graph = Array.from(Array(n + 1), () => [])
    for (const [src, dest] of edge) {
        graph[src].push(dest)
        graph[dest].push(src)
    }
    const distance = Array(n + 1).fill(0)
    distance[1] = 1
    const toBeSearched = [1]
    while (toBeSearched.length > 0) {
        const src = toBeSearched.shift()
        for (const dest of graph[src]) {
            if (distance[dest] === 0) {
                distance[dest] = distance[src] + 1
                toBeSearched.push(dest)
            }
        }
    }
    return distance.filter(x => x === Math.max(...distance)).length
}

b)상기 코드 바탕으로 재정의 해봤다.

function solution(n, edge) {
    let adjacencyList= [];
    for (let i=0; i<=n;i++){
        adjacencyList.push([]);
    }
    
    for (const [src, dest] of edge) {
        adjacencyList[src].push(dest)
        adjacencyList[dest].push(src)
    }
    const visited = Array(n + 1).fill(0)
    visited[1] = 1
    const Q = [1]
    while (Q.length > 0) {
        const src = Q.shift()
        for (const dest of adjacencyList[src]) {
            if (visited[dest] === 0) {
                visited[dest] = visited[src] + 1
                Q.push(dest)
            }
        }
    }
    return visited.filter(x => x === Math.max(...visited)).length
}

Math.max(...visited)) 쓰는게 더 좋아보인다.