[프로그래머스] Lv.03 네트워크 (JavaScript)

문제

프로그래머스

 

문제 설명

아래 사진과 같이 1번 컴퓨터와 2번 컴퓨터가 직접적으로 연결되어 있고, 2번 컴퓨터와 3번 컴퓨터가 직접적으로 연결되어 있을 때 1번 컴퓨터와 3번 컴퓨터도 연결되어 있다고 판단하기에 1, 2, 3번은 모두 연결되어 있다고 한다고 합니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 내트워크의 개수를 반환하면 되는 문제입니다.

 

※제한 사항

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

풀이

dfs를 활용하여 computer[i][j]가 0인 경우 방문한 경로일 경우까지 탐색을 진행하여 네트워크가 연결되어 있는 최대 범위를 찾아준 뒤 연결이 끊겨 있는 경우( computer[i][j]가 0인 경우 방문한 경로일 경우 ) 하나의 네트워크를 형성한 것이기에 숫자를 더해주는 방식으로 풀었습니다.

 

function solution(n, computers) {
    let cnt = 0; // 네트워크 개수를 저장하는 변수
    let visited = Array(n).fill(false); // 방문한 노드를 구분하기 위한 배열
    
    // 탐색을 진행합니다.
    // computers[node][neighbor]인 경우( 연결이 되어 있는 경우)
    // 아직 방문하지 않은 노드 일 경우
    // 위 경우가 만족되지 않을 때까지 진행합니다.
    const dfs = (node) => {
        visited[node] = true
        for(let neighbor = 0; neighbor < n; neighbor++){
            if(computers[node][neighbor] === 1 && !visited[neighbor]){
                dfs(neighbor)
            }
        }
    }
    
    // 모든 컴퓨터에 대해 탐색 진행
    for(let i=0; i<n; i++){
        if(!visited[i]){
            dfs(i)
            cnt++
        }
    }
    
    return cnt
}