[Programmers] 네트워크

문제

 

깊이/너비 우선 탐색(DFS/BFS) > 네트워크

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

 

 

아이디어

 

이번 문제의 아이디어는 문제 분류에도 나와있듯이 DFS/BFS입니다.

 

둘 중 아무거나 사용해도 문제는 풀 수는 있습니다.

 

저 같은 경우는 DFS를 이용하여 풀었습니다.

 

풀이법은 다음과 같습니다.

 

1. 컴퓨터를 탐색

2. 아직 방문하지 않은 컴퓨터면 방문 체크 후 DFS로 주변 컴퓨터들 탐색

3. 모든 컴퓨터를 방문할 때까지 1~2를 반복

 

 

구현 코드 (JavaScript)

 

const solve = (i, n, computers, visited) => {
    for(let a=0; a<n; a++) {
        if(computers[a][i] === 1 && visited[a] === false) { // 다른 컴퓨터와 연결되어 있고 해당 컴퓨터를 방문한적이 없는 경우
            visited[a] = true;
            
            solve(a, n, computers, visited);
        }
    }
}

function solution(n, computers) {
    let res = 0;
    const visited = new Array(n).fill(false); // 방문여부 체크
    
    for(let i=0; i<n; i++) {
        if(!visited[i]) { // 아직 방문한적이 없는 경우
            visited[i] = true; // 방문 체크
            solve(i, n, computers, visited); // DFS로 탐색
            res++; // 네트워크 개수 증가
        }
    }
    
    return res;
}

 

 

 

읽어주셔서 감사합니다.