[백준 1325번] BFS(너비 우선 탐색) - 효율적인 해킹

✨ 문제 ✨

✨ 정답 ✨

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')
const [N, M] = input.shift().split(' ').map((el) => +el)

let array = input.map((el) => el.split(' ').map((el2) => +el2))
let graph = Array.from({ length: N + 1 }, () => []);

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

let answerIndex = [];
let max = 0;
const solution = (start) => {
    let count = 0;
    let answer = 0;
    let queue = [start]
    let visited = new Array(N + 1).fill(false)
    while (queue.length) {
        let current = queue.shift();
        if (answer < count) {
            answer = count;
        }

        visited[current] = true;
        count += 1;
        let nextIs = graph[current];
        for (let i = 0; i < nextIs.length; i++) {
            if (visited[nextIs[i]] === true) {
                continue;
            } else {
                queue.push(nextIs[i])
                visited[nextIs[i]]=true;

            }
        }
    }
    // 여기에서 인덱스값만 리턴해줘야 함.
    // 최대값을 위에서부터 찾아내야 함.
    if (max < answer) {
        max = answer;
        answerIndex = [];
        answerIndex.push(start)
    } else if (max === answer) {
        answerIndex.push(start);
    }
}

for (let i = 1; i <= N; i++) {
    solution(i)
}

console.log(answerIndex.join(' '))



// 실패(시간초과)
// input = input.split('\n')
// const [N, M] = input.shift().split(' ').map((el) => +el)

// let array = input.map((el) => el.split(' ').map((el2) => +el2))
// let graph = Array.from({ length: N + 1 }, () => []);

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

// // 해킹 가능한 컴퓨터 수 배열(컴퓨터 번호는 인덱스로 처리)
// let countArray = new Array(N + 1).fill(0);
// const solution = (start) => {
//     // 해킹 가능한 컴퓨터 수
//     let count = 0;
//     let queue = [start]
//     let visited=new Array(N+1).fill(false)
//     while (queue.length) {
//         let current=queue.shift();
//         if (visited[current]===true){
//             continue;
//         }
//         visited[current]=true;
//         count+=1;
//         let nextIs = graph[current];
//         for (let i=0;i<nextIs.length;i++){
//             if (visited[nextIs[i]]===true){
//                 continue;
//             }
//             queue.push(nextIs[i])
//         }
//     }
//     return count;
// }

// for (let i = 1; i <= N; i++) {
//     countArray[i]=solution(i)
// }

// let max=Math.max(...countArray)
// console.log(countArray.filter((el)=>el===max).join(' '))

🧵 참고한 정답지 🧵

💡💡 기억해야 할 점 💡💡

시간초과 때문에 고생했다. 해킹 가능한 수로 이루어진 배열을 얻은 다음에 최대값을 뽑아내고, 해당 값을 가진 인덱스를 출력했는데 시간초과가 떴다.
애초에 solution() 함수에서는 최대값을 가진 인덱스값만을 리턴해주었어야 한다.
한 번 반복을 할 때 최대한 많은 계산을 넣어두어야 하는 것 같다.
어렵다.