[boj 11724] 연결 요소의 개수 -js

// 연결 요소의 개수

const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');

const [N, M] = input[0].split(' ').map(Number);
const arr = input.slice(1);

const sol = (N,M,arr) =>{
    const graph = Array.from(Array(N+1), () =>new Array());
    const visited = new Array(N+1).fill(false);
    let count = 0;

    for(const item of arr){
        const [node1, node2] = item.split(' ').map(Number);
        graph[node1].push(node2);
        graph[node2].push(node1);
    }

    const dfs = (v) =>{
        visited[v] = true;
        for(const node of graph[v]){
            !visited[node] ? dfs(node) : null;
        }
    }

    for(let i=1; i<=N; i++){
        if(!visited[i]){
            dfs(i);
            count++;
        }
    }
    console.log(count);
}

sol(N,M,arr);

dfs를 활용한 기본문제 인 것 같다.

순조롭게 풀던 도중 예상하지 못한 결과가 나왔는데 바로 시간초과였다..

풀이는 전혀 문제가 없어보여 바로 검색을 해보았다. 

알고리즘을 풀 때 주의사항 을 발견하였고 shift() 를 사용할 때 시간초과가 날 수 있다는 것이였다.

 

shift 연산은 주의해서 사용하자!! 하나 또 배워 기분좋게 잘 수 있겠다!

 

+ 자연스럽게 그럼 큐를 사용할 때 js에선 shift를 사용해 구현했는데 큐를 어떻게 구현하지? 라는 궁금증이 생겼다. js로 큐를 구현해봐야겠다!