[코딩테스트 javascript] 네트워크 - DFS , 그래프 탐색 알고리즘

네트워크

 

프로그래머스

 

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

첫 번째 시도,

테스트는 시도했다.

실패한 이유는 BFS로 풀었고,

아래 코드는 첫번째 요소와 마지막 요소가 연결되어 있는 경우 카운트의 횟수가 다르다.

 

function solution(n, computers) {
    let visited = computers.map(v=>false)
    computers.sort().reverse()
    console.log(computers)
    // BFS - 연결조건
    let q = [0];
    while(q.length) {
        const i = q.shift();
        if (visited[i]===false) {
            visited[i] = i;
            for (let n=i+1;n<visited.length;n++) {
                if (computers[i][n]===1) {
                    visited[n] = i
                }
            }
            if(i+1<computers.length) q.push(i+1)
        }    
    }
    
    
    return [...new Set(visited)].length;
}

채점 결과

정확성: 46.2

 

합계: 46.2 / 100.0

 

 

풀이과정

 

1. DFS - 깊이탐색알고리즘

2. 컴퓨터 Array의 원소만큼 재귀함수를 동작하는 코드를 작성한다.

let visited = Array(n).fill(false)
let count = 0;

// 재귀함수 수행 조건
arr.forEach((v,i)=>{
	if (visited[i]===false) {
    	DFS(i) 
        count++
    }
})

3. 재귀함수 작성

function DFS(node) {
	if(!visited[node]) {
    	visited[node]=true;
        computers.map((v,i)=>{
        	// arr[node]의 1을 확인하는 코드
        	if (v[node]===1 && visited[i] === true) {
            	DFS(i) }
        })
    }
 }

 

4. 전체 코드

function solution(n, computers) {
    // DFS 재귀 함수 
    let count = 0;
    let visited = Array(n).fill(false);
    
    const DFS = (node) => {
        visited[node] = true;
        computers.map((v,i)=>{
            if(v[node]===1 && !visited[i]) {
                visited[i]=true;
                DFS(i);
            }
        })
       
    }
    
    computers.forEach((v,i)=> {
        if (!visited[i]) {
            DFS(i);    count++;}})   
    console.log(visited)
    return count
}