[JS] 프로그래머스 네트워크 DFS 풀이

 

 

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

 

 

 

 

 

쉬워보이지만 마냥 쉽지 않은 DFS Lv.3 문제.

BFS를 풀 때 일단 무지성 큐 생성하고 시작하는 것처럼

DFS도 무지성 stack을 생성하고 방식으로 풀고 싶었다.

찾아보니 굳이 이렇게 풀지 않는 사람들도 많은 것 같다

(어차피 로직은 비슷하니까 굳이 싶어서 인 것 같음)

 

stack를 직관적으로 이해하고 싶어서 이 방법을 선택

 

function solution(n, computers) {
    let visited = Array(n).fill(false); // 방문 check는 국룰

    const stack = [];
    let cnt = 0; //해를 구했을 때마다 카운팅
    const dfs = (start) => {
        stack.push(start); //stack 에 0 삽입
        while (stack.length > 0) {
            const num = stack.pop();
            if (!visited[num]) {
                //당연히 안걸림 0은 1빠니까
                //필터링을 또 하는 이유?
                visited[num] = true; //방문체크~!
                computers[num].forEach((ele, idx) => {
                    // 이차원 배열 돌거디~
                    if (ele == 1 && num !== idx) {
                        //연결된 애들의 넘버를 check~! 본인 제외
                        stack.push(idx); // 다음 차례인 애들을 stack에 삽입하면?
                        // DFS라는 함수를 다시 실행시키기 전에 while문을 다시 돌게 됨
                        // stack.length가 0이 되면 실행중지하기 때문에
                        // start 0에서 뻗어나간 애의 연결이 끝날 때까지(그게 dfs다...)
                        // 함수가 진행되는 구조이다.
                        // 그러니까 dfs가 끝나면 cnt+1을 하는 거임
                        // 함수가 끝났다? while문이 종료됐다-> 해답을 찾았다->0에서 출발한 연결은 끝인겨
                        //그럼? dfs함수 실행시키는  for문으로 다시돌아가는 거
                    }
                });
            }
        }
    };

    for (let i = 0; i < n; i++) {
        //  컴퓨터 개수만큼은 돌기
        if (!visited[i]) {
        // 0이 들어갔다는 전제하에 주석 작성
            // 0부터 넣을게요. 아직은 다 false
            dfs(i); // 0 함수실행
            cnt++; //한 개의 연결이 모두 종료됐을 때 비로소 cnt +1
        }
    }

    console.log(cnt);
    return cnt;
}

solution(3, [
    [1, 1, 0],
    [1, 1, 0],
    [0, 0, 1],
]);

solution(3, [
    [1, 1, 0],
    [1, 1, 1],
    [0, 1, 1],
]);