프로그래머스 - 네트워크

Programmers - 네트워크

 

코딩테스트 연습 - 네트워크

 

---

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

 

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

문제 풀이

이 문제는 그래프 탐색(DFS/BFS) 으로 분류된 문제이다. 그래서 언뜻 보았을 때에는 한 노드부터 출발해서 도달할 수 있는 노드들을 BFS로 탐색해나가면서 이미 방문한 노드들은 제외하면 부분 그래프의 개수를 알 수 있다.

 

하지만 더 좋은 방법이 있다. 그것은 바로 union-find 알고리즘을 사용하는 것이다. 이 문제처럼 노드들 간의 연결 정보를 구할 때 정말 적합한 알고리즘이다. union-find 알고리즘은 쉽게 말해서 연결되어 있는 노드들을 트리 형태로 가지고 있는 것을 말하고, 같은 트리에 있는 노드들은 서로 연결된 노드라고 받아들이는 것이다.

const parent = Array.from(new Array(n), (_, i) => i);

// 부모 노드를 이용해 트리를 합침
const union = (a, b) => {
	const pA = find(a);
	const pB = find(b);
	    
	parent[pA] = pB;
};

// 자신의 부모 노드를 초기화해줌
const find = (x) => {
	if(parent[x] === x) return x;
	    
	parent[x] = find(parent[x]);	// 최적화
	return parent[x];
};

이 알고리즘을 사용한다면 각 노드들을 순회하면서 자신과 연결되어 있는 노드들을 모두 union 해버린 후, 마지막에 find를 통해서 총 몇 개의 트리가 생성되어 있는지 확인해주면 된다.

function solution(n, computers) {
    const parent = Array.from(new Array(n), (_, i) => i);
    const union = (a, b) => {
        const pA = find(a);
        const pB = find(b);
        
        parent[pA] = pB;
    };
    
    const find = (x) => {
        if(parent[x] === x) return x;
        
        parent[x] = find(parent[x]);
        return parent[x];
    };
    
    for(let i=0; i<computers.length; i++){
        for(let j=i; j<computers.length; j++){
            if(!computers[i][j]) continue;
            
            union(i, j);
        }
    }
    
    return parent.reduce((p,c) => {
        p.add(find(c));
        return p;
    }, new Set()).size;
}

JavaScript 결과