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] 이렇게 넣어서 구조분해 할당 하는식으로 했었는데
코드를 천천히 살펴보니 불필요한 부분이라서 배열을 제거했더니 시간초과였던 코드가 통과됬다..
이유는 찾아보고 추가해야겠다