Portfolio

문제

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Constraints:

1 <= n <= 200

n == isConnected.length

n == isConnected[i].length

isConnected[i][j] is 1 or 0.

isConnected[i][i] == 1

isConnected[i][j] == isConnected[j][i]

풀이

재영

💡

전형적인 유니온 파인드 문제이다.

최적화를 하려면 어떻게 할까? 간선을 체크한 것을 줄이면 된다.

양방향이므로, 2차원 배열에서 대각선을 기점으로 한 영역을 택하면 된다. 나의 경우 위의 것을 택한다. 이유는 위의 것은 더 많은 경우의 수들을 우선적으로 탐색하기 때문이다.

유니온 파인드를 실시한다. 이때, 일반적인 경우에서는 마지막 parents 역시 findParent를 실행하여 최종적인 노드를 업데이트 해야 한다. 그렇지만 이 연산은 O(N)으로 비싸다. (경로 압축으로 인한 최적화로 findParent는 여기서 이미 상수에 가깝다.) 이를 최적화하기 위해 Set 자료구조를 쓴다.

Set 자료구조에서 삽입과 삭제는 O(1)이므로 업데이트될 때마다 병합된 노드만 전체에서 삭제해주면 된다. 이것이 가능한 이유는, 우리는 연결의 구조가 중요한 게 아니라, 어떤게 병합이 되지 않은 루트인지만 추려내면 되기 때문이다. 또한 공간복잡도 역시 O(N)으로 현재 최대와 동일하므로 문제 없다.

size getter method를 활용하여 결과를 반환한다.


const findParent = (x, parent) => {
  return (parent[x] === x) ? x : (parent[x] = findParent(parent[x], parent));
}

/**
 * @return: number; 
 * 병합당한 부모 노드의 값을 반환합니다.
 */
const unionParent = (a, b, parent) => {
    const parentA = findParent(a, parent);
    const parentB = findParent(b, parent);
    
    if (parentA < parentB) {
        parent[parentB] = parentA;
        parent[b] = parentA;
        return parentB;
    }
    else if (parentA > parentB) {
        parent[parentA] = parentB;
        parent[a] = parentB;
        return parentA;
    }
}

const findCircleNum = (isConnected) => {
    const rowLength = isConnected.length;
    const colLength = isConnected[0].length;

    const parent = Array.from({ length: isConnected.length }, (_, idx) => idx);
    
    const set = new Set(parent);

    for (let i = 0; i < rowLength; i += 1) {
        for (let j = i; j < colLength; j += 1) {
            if (!isConnected[i][j] || i === j) continue;

            const loser = unionParent(i, j, parent);
            set.delete(loser);
        }
    }
    
    return set.size
};

효성


/**
 * @param {number[][]} isConnected
 * @return {number}
 */


var findCircleNum = function (isConnected) {
    const parent = [];

    for (let i = 0; i < isConnected.length; i++) {
        parent[i] = i;
    }

    const getParent = (x) => {
        if (parent[x] === x) return x;
        return parent[x] = getParent(parent[x]);
    }

    const unionParent = (a, b) => {
        const n1 = getParent(a);
        const n2 = getParent(b);
        if (n1 < n2) return parent[n2] = n1;
        else return parent[n1] = n2;
    }

    for (let i = 0; i < isConnected.length; i++) {
        for (let j = 0; j < isConnected[0].length; j++) {
            if (i !== j && isConnected[i][j]) {
                unionParent(i, j);
            }
        }
    }  
    parent.forEach((p, i) => {
        parent[i] = getParent(p);
    });

    return new Set(parent).size;
};

Number of Provinces

문제

풀이