문제

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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입니다.

입출력 예시

n	computers	return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

통과한 풀이

아이디어

• JavaScript의 내장 객체인 Map을 활용하여 노드 간 연결을 더욱 직관적인 자료구조에 담는다.
• visited 배열(원소는 boolean)을 두어서 방문했던 노드와 그렇지 않은 노드들을 구분한다.
• Array.prototype.some()과 Array.prototype.findIndex() 메소드를 이용하여 visited 배열에 더 이상 false가 없을 때까지 while문을 돌리고, false가 있다면 첫 번째 false인 노드를 반환하도록 한다.
• DFS 방법으로 visited 배열을 true로 채워나간다.

코드

function solution(n, computers) {
    let map = new Map();
    let visited = new Array(n).fill(false);
    let count = 0;
    
    //네트워크의 정보를 저장하는 Map을 완성시키기
    for(let i=0; i<n; i++) {
        map.set(i, []);
        for(let j=0; j<n; j++) {
            if(i === j) continue;
            
            let temp = map.get(i);
            if(computers[i][j])
                map.set(i, temp.concat(j));
        }
    }
    
    function dfs(node) {
        visited[node] = true;
        let toVisit = map.get(node);

        for(let i=0; i<toVisit.length; i++) {
            let nextNode = toVisit[i];
            if(visited[nextNode]) continue;
            else dfs(nextNode);
        }
        
    }
    
    // visited가 false인 노드가 없을 때까지
    while(visited.some(tf => tf === false)) {
        count++; 
        // 방문하지 않은 노드들 중 처음의 노드를 startNode로 잡는다.
        let startNode = visited.findIndex(node => node === false);
        dfs(startNode);
    }
    
    return count;
}

더 좋은 풀이

물론 Map 객체를 활용하지 않고도 알고리즘을 풀 수 있다. 그 중에서 가장 깔끔한 다른 사람의 코드를 가져와서 이해해 보았다.

알고리즘

일단, 컴퓨터가 n대 있으면 우리가 받는 computers 배열은 n * n 짜리의 배열이라는 것은 알고 있어야 한다. 또한, 나와 마찬가지로 visited 배열을 두어 방문했던 노드와 그렇지 않은 노드들을 구분해준다. (원소 또한 boolean형)

• 우선, 각 컴퓨터마다 각각의 연결정보(subnet이라고 칭하자)는 computers[i]에 저장되어 있다. 그래서 각 컴퓨터마다 DFS함수를 돌려준다.
• DFS 함수에서는 다음과 같은 일을 한다.
  • 우선 파라미터로 넘어온 노드(컴퓨터)에 대해서 방문처리를 해준다. (visited 배열에서 true로 바꿔줌)
  • 그리고 해당 컴퓨터의 연결정보(subnet)를 순회하면서 자기 자신과 이미 방문했던 노드를 제외하고, 만약 해당 컴퓨터와 연결이 되어있다면(subnet에서 1로 표시됨) 해당 노드를 그것의 subnet과 함께 다시 DFS에 넘긴다.

코드

const solution = (n, computers) => {
    let result = 0;
    const visited = new Array(n).fill(false);

    const DFS = (subnet, node) => {
        visited[node] = true;

        for (let k = 0; k < n; k++) {
            if (node === k || visited[k]) continue;
            if (subnet[k] === 1) {
                DFS(computers[k], k);
            }
        }
    };

    for (let i = 0; i < n; i++) {
        if (visited[i]) continue;

        DFS(computers[i], i);
        result++;
    }

    return result;
};

파이썬 코드

def solution(n, computers):
    answer = 0
    graph = [[] for _ in range(n)]
    #일단 그래프 정보를 입력하자 (자기 자신은 포함 X)
    for idx, info in enumerate(computers):
        for j, connected in enumerate(info):
            if connected and j != idx:
                graph[idx].append(j)
    
    visited =  [False] * n
    
    #DFS 함수
    def dfs(com):
        if not visited[com]:
            # 먼저 자기 자신을 방문처리
            visited[com] = True
            # 자기와 연결된 컴퓨터 리스트를 얻어낸다
            connects = graph[com]
            for node in connects:
                dfs(node)
        else:
            return
        
        
    #그래프를 가지고 재귀를 돌자
    startNode = 0
    while not all(visited):
        startNode = visited.index(False)
        dfs(startNode)
        answer += 1
    
    return answer