백준 1325번: 효율적인 해킹(javascript, DFS)

문제는 쉬웠지만 시간관리를 잘해야 하는 문제였다. 문제는 기본적인 문제인데 트리 구조를 만든 후 부모노드를 통해 자식 노드의 개수들을 세는 문제였다. 최대값을 찾아야 하므로 완전탐색을 이용해야 함을 알 수 있었고 N이 10^4로 좀 컸지만   시간제한이 5초로 매우 넉넉하여 쉽게 풀 수 있을것 같았다.

 

그러나 시간초과가 여러번 났는데 트리를 탐색하는 방법에 문제가 아닌 트리를 배열로 표현하기 위해 배열을 선언하는 과정에서 문제가 있음을 알 수 있었다.

 

먼저 원래의 배열 선언 코드는 다음과 같다.

let tree = new Array(N+1)
for(let i=0; i <= N; i++){
    tree[i] = new Array()
}

for (let i=1; i<= M; i++){
    const [a,b] = inpu[i].split(' ').map(c => Number(c))
    tree[b].push(a)
}

문제에서 트리는 단방향 트리이므로 부모노드의 인덱스에만 자식노드의 인덱스를 넣어 주었다. 문제가 되는 부분은 for문을 두번씀으로써 시간복잡도가 2O(N)이 된 부분인데 사실 시간제한이 넉넉하고 이차원 배열을 통한 트리 탐색방법의 시간복잡도가 커서 이정도는 문제가 안될줄 알았다. 

 

그러나 실제로는 그렇지 않았는데 이 배열선언 부분만 바꿔줘도 문제가 풀리는 것을 볼 수 있었다.

배열을 선언하는 부분을 고쳐 통과한 코드는 다음과 같다.

 

const fs = require('fs');
const inpu = fs.readFileSync("/dev/stdin").toString().trim().split('\n');

function dfs(node){
    visited[node] = true
    for(const leaf of tree[node]){
        if (!visited[leaf]){
            cnt++
            dfs(leaf)
        }
    }
}

const [N,M] = inpu[0].split(' ').map(a => Number(a))

const tree = Array.from({ length: N + 1 }, () => []);

for (let i=1; i<= M; i++){
    const [a,b] = inpu[i].split(' ')
    tree[b].push(a)
}

let cash = []
let max = Number.NEGATIVE_INFINITY
for(let i=1; i<=N; i++){
    cnt = 0
    visited = new Array(N+1).fill(false)
    dfs(i)
    if(cnt >= max){
        max = cnt
        cash.push([i,cnt])
    }
}

let answer = []
for(const ca of cash){
    if(ca[1] === max){
        answer.push(ca[0])
    }
}

console.log(answer.join(' '))