백준, 11724 연결 요소의 개수

백준, 11724 연결 요소의 개수 javascript

📖 https://www.acmicpc.net/problem/11724

👨‍💻 문제

문제 풀이

1. 연결 요소가 무엇인가?
   

2. 그냥 BFS로 문제를 풀어보기로 했다!
   • BFS로 문제를 풀면, 각 start지점을 기준으로 BFS한 배열들이 출력된다.
   • 배열들이 중복된 경우를 제외하고, answer을 카운팅한다.

💻 제출한 코드

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

const [vertex, edge] = [...input.shift().split(' ')];

class BFS {
    constructor() {
        this.list = {};
        this.vistiedVertex = {};
    }

    addVertex(val) {
        this.list[val] = [];
    }

    addEdge(vertex1, vertex2) {
        this.list[vertex1].push(vertex2);
        this.list[vertex2].push(vertex1);
    }

    bfs(start) {
        const queue = [start];
        const result = [];
        const vistied = {};
        vistied[start] = true;

        let shifted;
        while(queue.length) {
            shifted = queue.shift();
            result.push(shifted);
            this.list[shifted].forEach((neighbor) => {
                if(!vistied[neighbor]) {
                    vistied[neighbor] = true;
                    queue.push(neighbor);
                }
            })
        }
        result.forEach((item) => this.vistiedVertex[item] = true)
        return result;
    }
}

const b = new BFS();
for(let i=1; i<=vertex; i++) {
    b.addVertex(i)
}

input.forEach((item) => {
    b.addEdge(item.split(' ')[0], item.split(' ')[1]);
})

let answer = 0;
for(let i=1; i<=vertex; i++) {
    if(!b.vistiedVertex[String(i)]) {
        b.bfs(String(i));
        answer++;
    }
}

console.log(answer);

이번 문제를 풀면서,

• 문제는 무난히 맞았는데...
• 내 코드는 다른 사람들 코드보다 길다. 😂
• 자료구조를 배우면서 배웠던 bfs, dfs의 코드 스타일을 적용하지 않으면 여전히 문제를 풀긴 힘들다.
• 그래서 다른 사람의 코드를 보면서, 조금 쉽게 적용하는 방법이 없는지 고민하고 있다.