[백준 11725번] BFS(너비 우선 탐색) - 트리의 부모 찾기

✨ 문제 ✨

✨ 정답 ✨

const fs = require("fs");
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')
const N=+input.shift();
let graph=[];
let answer=[];


for (let i=0;i<=N;i++){
    graph[i]=[];
}

input.forEach((edge)=>{
    const [from, to]=edge.split(' ').map((el)=>+el);
    graph[from].push(+to);
    graph[to].push(+from);
})


const BFS=(start)=>{
    const visited=new Array(N+1).fill(false);
    visited[start]=true;
    const queue=[start];

    while(queue.length){
        const current=queue.shift();
        for (let i=0;i<graph[current].length;i++){
            const next=graph[current][i];
            if (!visited[next]){
                visited[next]=true;
                answer[next]=current;
                queue.push(next);
            }
        }
    }
}


BFS(1);
let result="";
answer.forEach((el)=>result+=el+"\n");
console.log(result)

🧵 참고한 정답지 🧵

https://kscodebase.tistory.com/412

💡💡 기억해야 할 점 💡💡

1. console.log()를 반복적으로 사용하면 시간이 오래 걸린다.
2. 이전과는 다르게 graph를 이용함.
3. current가 next의 부모가 된다는 것.

    for (let i=0;i<graph[current].length;i++){
         const next=graph[current][i];
         if (!visited[next]){
             visited[next]=true;
             answer[next]=current;
             queue.push(next);
         }
    }