네트워크 / js 풀이

프로그래머스 : 네트워크

https://programmers.co.kr/learn/courses/30/lessons/43162

문제풀이

프로그래머스 3단계 풀이에 해당하는 문제입니다. 사실 평범한 DFS/BFS 문제이며 복잡하지 않습니다.

행렬이 연결되어 있으면 1이고 연결되어 있지 않으면 0인데, 방문을 체크하며 연결되어있는 요소에서 재귀적으로 함수를 실행하면 됩니다.

 

코드

function solution(n, computers) {
    var answer = 0;
    let tmp = Array.from({length: 200}, () => false);  // 방문체크용 배열

    function dfs(start){  // 재귀함수
        tmp[start] = true;  // 방문체크

        for(let i=0; i<n; i++){
            if(!tmp[i] && computers[start][i] === 1){
            // 방문하지 않았고, 연결되어 있다면
                dfs(i);  // 재귀적으로 탐색
            }    
        }
    }

    for(let j=0; j<n; j++){  // 컴퓨터 갯수만큼 탐색
        if(!tmp[j]){  // 방문을 하지 않았다면
            dfs(j);  // 함수 실행
            answer ++;
        }
    }

    return answer;
}

 

리뷰

DFS 알고리즘을 사용하여 풀이 하는 문제에 대해 익숙하다면 금방 풀 수 있을 것 같습니다!