[코딩테스트]백준 - 연결 요소의 개수(11724)

문제

연결 요소의 개수(11724)

해결한 코드

const fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const NAndM = input[0].split(' ')
const N = +NAndM[0]
const M = +NAndM[1]
let links = []
for (let i = 1; i < input.length; i++) {
    links.push(input[i].split(' ').map((e) => +e))
}

function makeGroupState() {
    let groupStateTable = []
    for (let i = 0; i <= N; i++) {
        groupStateTable.push(i)
    }
    return groupStateTable
}

function changeGroupState(start, end, groupStateTable) {
    let endValue = groupStateTable[end]
    for (let i = 1; i < groupStateTable.length; i++) {
        if (groupStateTable[i] === endValue) groupStateTable[i] = groupStateTable[start]
    }
    return groupStateTable
}

function findConnectedComponents(links, groupStateTable) {
    for (let link of links) {
        const start = link[0]
        const end = link[1]
        if(groupStateTable[start] !== groupStateTable[end]){
            groupStateTable = changeGroupState(start, end, groupStateTable)
        }
    }
    const result = new Set(groupStateTable.slice(1, groupStateTable.length))
    return [...result].length
}
if(N === 1){
    console.log(1)
    return 
}

if(M === 0) {
    console.log(N)
    return 
}

let groupStateTable = makeGroupState()
const answer = findConnectedComponents(links, groupStateTable)
console.log(answer)

풀이

1. Union-Find로 그룹이 몇개인지 계산한다.

입력으로 받아온 정점 연결의 정보를 통해 어떻게 grouping 되어지는지 계산한다.
ex. 문제의 입력 예제로 예를 들면

6 5
1 2
2 5
5 1
3 4
4 6

이렇게 2개의 그룹이 만들어진다.

그룹이 어떻게 만들어지는지는 다음과 같은 방식으로 확인할 수 있다.

초기값으로 각 정점마다 연결된 정점을 자기자신으로 둔다.

이제 [1, 2] 가 연결되었다는 입력이 들어오게 되면

테이블[2] 의 값을 테이블[1]의 값과 같게 만들어줌으로써 1과 2를 서로 연결시킨다.

[2, 5] 가 들어오면

테이블[5]의 값을 테이블[2]의 값과 같게 만들어 2과 5를 연결시킨다.

[5, 1]이 들어오면?

• 테이블[5]의 값은 테이블[1]의 값과 같다.
• 즉, 이미 둘은 연결되어있는 것과 다름 없으므로 무시한다.

[3, 4]가 들어오면?

테이블[3]과 테이블[4]의 값을 같게 만들어 3과 4를 연결시킨다.

[4, 6]이 들어오면?

테이블[4]와 테이블[6]의 값을 같게 만들어 4와 6을 연결시킨다.

연결이 종료되었다.
그럼 이제 테이블의 정보를 통해 몇개의 그룹으로 연결되었는지 확인할 수 있다.

값이 1과 3뿐이다.
총 2개의 그룹으로 연결되었음을 알 수 있다.

2. 연결된 개수를 출력한다.

※ 정점이 1개거나 간선이 0개일 때와 같은 경우를 고려하며 값을 출력한다.

연결 요소를 세어줄 때
처음엔 for문을 돌리면서 some 함수로 해당 숫자가 기존에 셌던 숫자인지 판별하는 방식으로 접근했는데, 시간이 무지 걸렸다.. ㅜㅜ
다음 방식으로 Set을 사용했는데, 시간은 좀 개선되었지만 눈에 띄게 좋아졌다고 하기는 약간 어려운 정도..
더 좋은 방식으로 풀어낸 다른 사람의 코드를 보면서 공부해야겠다.
귀찮다고 그냥 넘어가기 보다는 꼼꼼하게 짚고 넘어가는게 역시 모든 공부의 국룰인듯..