프로그래머스 - 네트워크

문제

• 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 말한다.
• 예를들어 컴퓨터A가 컴퓨터B와 직접적으로 연결되어있고, 컴퓨터B가 컴퓨터C와 직접적으로 연결되어있다면, 컴퓨터A와 컴퓨터C는 간접적으로 연결되어 정보를 주고 받을 수 있다. 따라서 컴퓨터A,B,C는 모두 같은 네트워크 상에 있다고 말할 수 있다.
• 컴퓨터의 갯수 n과 연결에 대한 정보가 주어질 때, 네트워크의 갯수를 반환하라.

입력값

• n(int): 컴퓨터의 갯수
• computers(int[][]): 컴퓨터들이 연결되어있는지 아닌지를 표현한 2차원배열. 컴퓨터i와 컴퓨터j가 연결되어있다면 computers[i][j]는 1이고 연결되어있지 않으면 0이다.

제한사항

• 1 <= n <= 200
• computers[i][i]는 항상 1 이다.

 

문제풀이

1. 한번 방문한 네트워크는 집합 seen에 넣어 다시 방문하지 않는다. 서로 연결되어있는 네트워크를 연결되어있지 않은 네트워크보다 먼저 방문한다. (DFS)
2. seen 집합에 추가되어있지 않는 컴퓨터를 방문시 새 네트워크에 진입했다는 의미이므로 네트워크 갯수를 카운트 업 해준다. 

function solution(n, computers) {
    const seen = new Set()
    const dfs = i => {
        seen.add(i)
        for (const j in computers) {
            if (!seen.has(j) && computers[i][j]) {
                dfs(j)
            }
        }
    }
    let answer = 0
    for (const i in computers) {
        if (!seen.has(i)) {
            answer++
            dfs(i)
        }
        
    }
    return answer
    
}

시간복잡도: O(N)

공간복잡도: O(N)