[백준 1389번] DP(다이나믹 프로그래밍) - 케빈 베이컨의 6단계 법칙

✨ 문제 ✨

✨ 정답 ✨

const { count } = require("console");
const fs = require("fs");
const { nextTick } = require("process");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./예제.txt";
let input = fs.readFileSync(filePath).toString().trim();

// const fs = require('fs'); 
// let input = fs.readFileSync('/dev/stdin').toString().trim();


input=input.split('\n').map((item)=>item.split(' ').map((el)=>+el))
// N: 유저의 수, M: 친구 관계의 수
const [N, M]=input.shift();
const graph=Array.from({length:N+1}, ()=>[])
const result=[];

for (let i=0;i<M;i++){
    const [A, B]=input[i];
    graph[A].push(B);
    graph[B].push(A);
}

const BFS=(start, target)=>{
    const queue=[[start,0]];
    visited=Array.from({length:N+1}, ()=>false);
    while (queue.length){
        let [current, count]=queue.shift();
        let friends=graph[current];
        if (visited[current]){
            continue;
        }
        visited[current]=true;
        if (current===target){
            return count
        }
        for (let i=0;i<friends.length;i++){
            let friend=friends[i];
            if (visited[friend]){
                continue;
            }
                queue.push([friend, count+1])
            
        }
    }

}

for (let i=0;i<N;i++){
    let count=0;
    for (let j=1;j<=N;j++){
        count+=BFS(i+1,j);
    }
    result.push(count);
}

let min=Math.min(...result);
console.log(result.indexOf(min)+1)

🧵 참고한 정답지 🧵

💡💡 기억해야 할 점 💡💡