[BaekJoon] 11724번 연결 요소의 개수

▶ 문제 : https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

▶ 코드 :

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let N = 0; 
let E = 0;
const edges = [];

rl.on('line', function(line) {
    if(!N){
        [N, E] = line.split(' ').map(Number);
        if(E === 0){
           main();
           process.exit(); 
        }
    }else{
        edges.push(line);
        if(edges.length === E){
            main();
            process.exit();
        }
    }  
});

const main = () => {
    const graph = Array.from(Array(N), () => Array().fill([]));

    for (let i = 0; i < E; i++){
        const [x,y] = edges[i].split(' ').map(n => Number(n));
        graph[x-1].push(y-1);
        graph[y-1].push(x-1);    
    }

    const visited = Array(N).fill(false);

    let count = 0;
    for(let i = 0; i < N; i++){
        if(visited[i]){
            continue;
        }else{
            dfs(graph,visited,i);
            count+=1;        
        }
    }

    console.log(count);

    function dfs(graph, visited, start){
        visited[start] = true;
        const stack = [...graph[start]]

        while(stack.length > 0){
            const node = stack.pop();
            if(visited[node]){
                continue;
            }

            visited[node] = true;
            stack.push(...graph[node]);
        }
    }
}

 

▶ 문제 풀이 :

1. 너무 복잡하고 어렵게 풀었다. 초기 fs 로 데이터를 읽고 스프레드 문법(...)을 난사하면서 풀었던 코드에의해 메모리 초과가 계속 발생했다. 

2. 스프레드(...) 문법은 기존 배열을 쪼개 새로운 배열을 반환하기에 메모리 초과가 나나(?) 라는 의심을 하게 되었고, 스프레드 문법을 사용한 부분을 줄여보자 해서 다시금 작성하게 되었다. 또한 입출력 방식에 문제가 있는 것 같기도 해서 fs에서 readline을 이용한 방식으로 변경해보았다.

3. 초기 readline을 통해 읽어온 데이터를 파싱해 N, E, edges[] 를 초기화하고 main 메서드에서 로직을 처리한다.

4. main문에서는 edge데이터를 읽어 그래프를 생성하고 내부 정의함수 dfs()를 이용해 그래프들을 탐색한다. 결국 dfs에 의해 visited배열에 한번씩 변화가 생기고 dfs를 호출할때마다 count를 1씩 증가시키는 방식을 채택하였다. 

5. 너무 오래걸렸지만 그래도 해결했음에 뿌듯하고 다른 분들의 코드를 보다가 조금 더 깔끔하고, 이해가 잘되는 코드가 있었기에 가져와 보았다.

 

▶ 다른 유저의 풀이방법:

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [n, m] = input.shift().split(' ').map(Number);
const arr = input.map((el) => el.split(' ').map(Number));

const solution = (n, arr) => {
  let answer = 0;
  let visited = Array.from(Array(n + 1), () => 0);
  const graph = Array.from(Array(n + 1), () => []);
  for (let [a, b] of arr) {
    graph[a].push(b);
    graph[b].push(a);
  }
  const dfs = (node) => {
    visited[node] = 1;
    for (let next of graph[node]) {
      if (!visited[next]) {
        dfs(next);
      }
    }
  };

  for (let i = 1; i <= n; i++) {
    if (!visited[i]) {
      dfs(i);
      answer++;
    }
  }

  return answer;
};

console.log(solution(n, arr));

[출처] https://www.acmicpc.net/source/43991075