문제
해결한 코드
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을 사용했는데, 시간은 좀 개선되었지만 눈에 띄게 좋아졌다고 하기는 약간 어려운 정도..
더 좋은 방식으로 풀어낸 다른 사람의 코드를 보면서 공부해야겠다.
귀찮다고 그냥 넘어가기 보다는 꼼꼼하게 짚고 넘어가는게 역시 모든 공부의 국룰인듯..
