[javascript] 백준 1325번 효율적인 해킹

bjyyyyy·2023년 1월 15일
0

문제보기

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs
    .readFileSync(filePath)
    .toString()
    .trim()
    .split("\n")
    .map((item) => item.split(" ").map((value) => +value));

const [N, M] = input[0];
const graph = Array.from({ length: N + 1 }, () => []);
let answer = [];

// 인접리스트 
for (let i = 1; i <= M; i++) {
    let [a, b] = input[i];
    graph[b].push(a);
}

let max = 0; // 해킹할수 있는 컴퓨터의 최대 수
const DFS = (start) => {
    const stack = [start];
    const visited = Array.from({ length: N + 1 }, () => false);
    let count = 0; // 해킹 가능한 컴퓨터의 수 카운트
    let result = 0; // 해당 컴퓨터의 해킹 가능한 최대 수
    while (stack.length) {
        let cur = stack.pop();
        if (result < count) result = count;
        visited[cur] = true;
        for (let i = 0; i < graph[cur].length; i++) {
            let value = graph[cur][i];
            if (visited[value]) continue;
            visited[value] = true;
            count += 1;
            stack.push(value);
        }
    }
    if (max < result) { // 현재 해킹할수 있는 컴퓨터의 최대 수보다 이번 컴퓨터의 해킹 가능한 최대 수가 크다면
        max = result;
        answer = []; // 초기화
        answer.push(start);
    } else if (max === result) {
        answer.push(start);
    }
};

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

console.log(answer.join(" "));

시간초과와 메모리초과가 번갈아가면서 나와서 멘붕이 왔던 문제였다..
우선 N과 M을 헷갈려서 헤멘것도 있고
while문 안에서 stack에 start를 [start] 이렇게 넣어서 구조분해 할당 하는식으로 했었는데
코드를 천천히 살펴보니 불필요한 부분이라서 배열을 제거했더니 시간초과였던 코드가 통과됬다..
이유는 찾아보고 추가해야겠다

0개의 댓글