백준 - 11724 연결 요소의 개수

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오

입력

• 첫째 줄
  • 정점의 개수 N
  • 간선의 개수 M
• M개의 줄
  • 간선이 연결하는 두 정점의 번호 (u와 v)

제한 조건

• 1 ≤ N ≤ 1,000
• 0 ≤ M ≤ N×(N-1)/2
• 1 ≤ u, v ≤ N, u ≠ v

예시

// NOTE: 입력
6 5
1 2
2 5
5 1
3 4
4 6

// NOTE: 출력
2

// NOTE: 입력
6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

// NOTE: 출력
1

// NOTE: 입력
1 0

// NOTE: 출력
1

해결

고민한 부분

메모리 초과

• bfs에서 메모리 초과 에러가 발생

해결

1. visit 처리
   • 배열을 object로 변경, value는 boolean으로 처리
     • true일 경우, visited 이므로 continue
     • false일 경우, visited를 true로 변경
   • 개선 전
     • 배열로 처리하고 includes로 visit 여부를 확인
     • node가 많은 경우 탐색 시간이 오래 걸림
2. needVisit 처리
   • queue로 변경, visit이 아닌 경우에만 push
   • 개선 전
     • 그래프의 모든 노드를 needVisit에 넣음
     • node가 많은 경우 메모리가 터져버림

개선 전

const bfs = (graph, startNode) => {
    let _visited = [];
    let _needVisit = [];
    
    _needVisit.push(startNode);
    
    while(_needVisit.length > 0) {
        const _node = _needVisit.shift();
        
        if (!_visited.includes(_node)) {
            _visited.push(_node);
            
            if (!graph.has(_node)) break;
            
            const _adjacentNode = [...graph.get(_node)].sort((a, b) => a - b);
            _needVisit = [..._needVisit, ..._adjacentNode];
        }
    }
    
    return _visited;
};

개선 후

const bfs = (graph, startNode, visitedObj) => {
    const _queue = [startNode];

    while (_queue.length) {
        const _cur = _queue.shift();
        
        // NOTE: 이거 안 해주면, 간선이 없는 케이스 처리를 못 해 🥹
        if (!graph.has(_cur)) break;
        
        for (let node of [...graph.get(_cur)]) {
            if (visitedObj[node]) continue;
            
            visitedObj[node] = true;
            _queue.push(node);
        }
    }
};

오래 걸린 이유

• 예외 처리
  • start의 노드에 간선이 없는 경우

아니 이거 저번에 DFS 문제 풀다가 예외처리 안 해서 오래 걸렸는데 또 이렇게 오래 걸렸서
발전이 없으면 사람이 아니지 🙅🥹

전체 코드

const makeGraphMap = (inputData) => {
    const _map = new Map();
    
    for (let input of inputData) {
        const [_from, _to] = input.split(' ').map(Number);
    
        if (!_map.has(_from)) _map.set(_from, []);
        if (!_map.has(_to)) _map.set(_to, []);
        
        _map.get(_from).push(_to);
        _map.get(_to).push(_from);
    }
    
    return _map; 
};

const bfs = (graph, startNode, visitedObj) => {
    const _queue = [startNode];

    while (_queue.length) {
        const _cur = _queue.shift();
        
        // NOTE: 이거 안 해주면, 간선이 없는 케이스 처리를 못 해 🥹
        if (!graph.has(_cur)) break;
        
        for (let node of [...graph.get(_cur)]) {
            if (visitedObj[node]) continue;
            
            visitedObj[node] = true;
            _queue.push(node);
        }
    }
};

const makeCheckObj = (graph) => {
    const object = {};
    [...graph.keys()].forEach(v => object[v] = false);
    
    return object; 
};

const getConnectedComponent = (graph, n) => {
    let count = 0;
    const _visitedObj = makeCheckObj(graph);
    
    for (let i = 1; i < n + 1; i++) {
        if (_visitedObj[i]) continue;
        
        bfs(graph, i, _visitedObj);
        count += 1;
    }
    
    return count;
}

const solution = () => {
    // NOTE: inputs
    let [_conditions, ..._inputs] = require('fs')
        .readFileSync('dev/stdin')
        .toString()
        .trim()
        .split(/\n/);
    
    const _graphMap = makeGraphMap(_inputs);
    const [N, M] = _conditions.split(' ');
    const result = getConnectedComponent(_graphMap, +N);
    console.log(result);
};

solution();

---

출처

• 11724번: 연결 요소의 개수
• 11725번 반례