[JS] 네트워크

유니온 파인드를 사용해서 해결했다.

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

 

 

문제가 조금은 독특하게 주어졌다. 서로 이어져 있는것을 그래프 형태도 아니고 한번에 map으로 주어진 것도 아닌 형태로 주어졌다.

 

문제를 처음 딱 보자마자 union-find를 활용해서 네트워크에 맞는 컴퓨터들을 합쳐주면 되겠다! 라 생각을 했다.

 

set의 개수를 구하는 방법은 마지막에 틀릴 수 있다는 게 유니온-파인드를 쓴다면 조금 조심해야 할 부분이다.

왜냐면 union-find에서 당장의 부모는 다를 수 있기때문

 

예를 들어 0,1,2번 노드가 있다 생각해 보자.
[0,1,2]

 

1,2 번 유니온 처리
[0,1,1]

 

0,1 번 유니온 처리
[0,0,1]

 

분명 세개의 노드는 같이 연결되어있지만 당장 배열에 있는 값은 다르다.
따라서 마지막에 부모를 갱신해주는 for문이 존재한다

 

 

 

//union - find
const getParent = (n,arr) => {
    if (arr[n]===n) return n
    return arr[n] = getParent(arr[n],arr)
}

const union = (a,b,arr) => {
    a = getParent(a,arr)
    b = getParent(b,arr)
    if(a>b) arr[a] = b
    else arr[b] = a
}

function solution(n, computers) {
    //부모배열
    const parent = [...Array(n)].map((_,i) => i)
    //union 연산
    for (const computer of computers){
        const startIdx = computer.indexOf(1)
        for (let i = 0 ; i < n ; i++){
            if(computer[i]===1) union(startIdx,i,parent)
        }
    }
    // 부모 갱신
    for(let i = 0 ; i < n ; i++) getParent(i,parent)
    //set을 활용하여 영역파악
    return new Set(parent).size
}