Level3. 프로그래머스 네트워크(DFS/BFS) - JavaScript

 

function solution(n, computers) {
    let answer = 0;
    const visitedNode = [];
    
    for (let i = 0; i < n; i++) {
        if (visitedNode[i] !== true) {
            answer++;
            bfs(i);
        }
    }    
    
    return answer;

    function bfs(node) {
        visitedNode[node] = true;
        const q = [node];
        while(q.length !== 0) {
            const currentNode = q.shift();
            computers[currentNode].forEach((isConnected, nextNodeIndex) => {
                if (!isConnected || visitedNode[nextNodeIndex]) return;
                visitedNode[nextNodeIndex] = true;
                q.push(nextNodeIndex);
            })    
        }
    }
}

 

문제 설명

그래프 탐색 문제로 DFS 또는 BFS로 풀 수 있습니다.

그래프가 2차원 배열로 주어지며 어떤 정점 i가 다른 정점 k와 연결되어 있다면 computers[i][k]는 1입니다.

0은 연결된 간선이 없다는 의미입니다.

 

그렇다면 네트워크에 연결되어 있는 정점을 알기 위해 모든 정점을 탐색하면 됩니다. 

네트워크가 1개가 아닐 수 있기 때문에 방문하지 않은 정점을 찾아서 그래프 탐색을 다시 시작합니다. 

 

접근

컴퓨터를 정점으로 지칭하겠습니다.

모든 정점을 순회하면서 방문하지 않은  정점이 있다면 BFS탐색 시작

이때, 네트워크 개수 증가

 

bfs 탐색

정점, 2차원 배열, 방문 정점 배열을 파라미터로 받습니다.

큐에 정점을 넣고 방문 정점 체크를 하고 큐가 빌 때까지 while문을 돌려줍니다.

큐에서 앞에 있는 정점을 빼서 해당 정점에서 방문할 수 있는 정점이 있는지 확인합니다. 

있다면 큐에 넣고 방문 정점 체크