[개발일지] - 447(주말)

(1).백준 1043번 거짓말은 최근에 전공 공부를 하면서 봤던 알고리즘에서 배운 최소집합? 합 찾기 관련 내용으로

각각 대표되는 값 하나로 공통 내용들을 통일해서 index들이 각 위치를 대표하는 방식이었는데

해당 내용을 구현하기 위해 현재 index에 있는 값의 대표 주소값 확인용 find 메서드와

서로 다른 대표값들을 가진 그룹을 합치는 union 메서드를 구현해준 다음

 

진실을 알고 있는 그룹들을 먼저 union으로 엮어주고

각 파티에 참여한 사람들끼리 다시 그룹을 엮기 위해 union으로 합쳐준 다음

진실을 아는 그룹원과 각 파티의 그룹장을 비교해서 같지 않을 경우 count를 증가시켰고

진실을 아는 사람이 없으면 비교 없이 먼저 count를 증가시키게 비교했다.

 

처음에는 전체 그룹원과 비교했는데

글을 작성하면서 잘 보면 어차피 union을 먼저 했기 때문에

union을 하지 않은 상태에서 그렇게 처리하거나

아니면 union을 미리 돌린 상태에서 대표자 한번씩 비교 둘 중 하나만 해도 효율적으로 처리될 것 같다.

 

알고리즘 공부를 하면서 이것저것 보게 되는데

Class5에 최소 스패닝 트리라던지 전공에서 기본적으로 배우는 내용들이 여기저기 보이는데

의외로 백준 클래스를 순서대로 푸는게 확실히 도움이 되긴 하는 것 같기도 하고

전공자들이면 기본적으로 플래티넘까지는 쉽게 갈 것 같기도 하고 하여튼 배운게 바로바로 나오니 재미있었다.

const input = `3 4
1 3
1 1
1 2
2 1 2
3 1 2 3`.split('\n').map(el => el.split(' ').map(Number))

const [n, m] = input[0]
const know = input[1].slice(1)
const parent = []
let count = 0

for(let i = 0 ; i <= n ; i++){
    parent[i] = i
}

const find = (n) => {
    if (parent[n] != n) {
        parent[n] = find(parent[n])
    }
    return parent[n]
}

const union =  (a, b) => {
    const rootA = find(a)
    const rootB = find(b)
    
    if(rootA != rootB){
        parent[rootB] = rootA
    }
}

for(let i = 0 ; i < know.length - 1 ; i++){
    union(know[i], know[i + 1])
}

for(let i = 2 ; i < input.length ; i++){
    for(let j = 1; j < input[i].length - 1; j++){
        union(input[i][j], input[i][j + 1])
    }
}

for(let i = 2 ; i < input.length ; i++){
    if(know.length == 0 || find(input[i][1]) != find(know[0])){
        count++
    }
}

console.log(count)