[프로그래머스] 깊이/너비 우선 탐색(DFS/BFS) - 네트워크

참고 자료

[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)

나의답

function solution(n, computers) {
    // n: 컴퓨터 개수
    // computers[i][j]
    // i칸의 수와 같은 j 는 무조건 1임. -> 자기 자신이기 때문에    
    // 한쪽이 연결되면 반대쪽은 반드시 연결되어있음 -> 2번찾을 필요없음
    
    let answer = 0;
    
    const check = (computers, root, n) =>{
        for(let j = 0 ;j <computers.length ; j++){
            if(computers[root][j] == 1){
                 computers[root][j] = -1; //연결된 컴퓨터 체킹
                 computers[j][root] = -1; //반대쪽 역시 체킹
                check(computers, j, n) //재귀
             }
        }
    }
    
    for(let i = 0 ; i < computers.length ; i++){
        console.log(`${i} 번째 루트`);
        if(computers[i][i] != -1){
            //console.log("미방문 루트")
            answer++;
            check(computers, i, n)
        }else{
           // console.log("왔다감 ^^7 ")
        }    
    }
    
    return answer;
}

 

경로 탐색에는 넓이 우선 탐색과 깊이 우선 탐색이있는데

해당문제에서는 굳이 깊이로 안내려가도 되기에 넓이 우선 탐색을 했어야 하고

 

큐를 사용해서 문제를 해결하고 싶었지만, 참고했던 예제를 봐버려서 그런지, 재귀함수 방식에서 큐를 사용하는 방식으로 변환하는데는

실패했다...

 

이론은 이렇다

 

1. 루트 노드와 연결된 하위 노드를 큐에 전부 밀어 넣는다

2. 큐에 밀어 넣어진 노드 및 루트노트를 마킹한다

3. 루트노드에 연결된 모든 노드들이 큐에 들어갔다면 큐에서 앞에서 부터 1개씩 루트 노드로 삼아서 연결된 노드를 찾는다

4. 이때 2 번에서 마킹이 되었으면 넘어가고, 마킹이 안되었다면 마킹을 하고 해당 노드를 큐에 넣는다

5. 큐가 비워질때까지 반복한다

6. 큐가 비워지면 더이상 연결되어있는 네트워크가 없다는 뜻임으로 answer의 수를 1 증가시킨다(네트워크의 개수)

7. 다시 검색을해서 마킹이 되어있지 않은 노드를 찾아서 루트노드로 삼는다

8. 위의 과정을 모든 노드가 마킹이 될때까지 반복한다

 

이것이 넓이 우선 탐색방법이다.

 

즉, 루트 노드에 닿아있는 모든 노드들을 1층씩 훍어서 전부 마킹을 하고 넘어가는 형식이라고 생각하면 조금 이해가 쉬워진다.

 

다음번에는 꼭 큐로 다시 해보고 싶다