[DFS] 프로그래머스 '네트워크' - js

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/43162?language=javascript 

프로그래머스

2. 코드

https://bbeeyaks-moment.tistory.com/entry/%EC%99%84%EC%A0%84%ED%83%90%EC%83%89-%ED%8A%B8%EB%A6%AC-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%A0%84%EB%A0%A5%EB%A7%9D%EC%9D%84-%EB%91%98%EB%A1%9C-%EB%82%98%EB%88%84%EA%B8%B0-js

[완전탐색 & 트리] 프로그래머스 '전력망을 둘로 나누기' - js

해당 문제와 비슷한 네트워크 유형이지만 접근 방법은 확연히 다르다. 

곰곰히 생각해보니 전력망 문제는 엣지로 연결된? 노드들의 최댓값을 구해야해서 재귀함수 안에 count를 세는 부분이 들어가야하고, 이번 네트워크 문제는 연결된 노드들의 최댓값을 구하는게 아닌 네트워크(연결된 노드들의 덩어리)의 갯수를 구하는 것이기 때문에 재귀 함수 내에서는 그 어떤 것도 count 해줄 필요가 없다. 그래서 방문할 노드가 아닌 다른 파라미터들은 필요가 없는 것이다.

대신, 재귀함수를 호출하는 함수 안에서 재귀함수가 재호출된 경우에는 앞에서 노드 간의 연결이 더 이상 없어 dfs 함수가 종료되었다는 이야기 이므로 덩어리 갯수 +1 을 해줘야한다.

 

dfs 파라미터

• node : 방문할 노드

function solution(n, computers) {
    let visited = new Array(n).fill(0);
    let answer = 0;

    function dfs(node) {
        visited[node] = 1;
        for(let i=0;i<computers[node].length;i++) {
            if(computers[node][i]===1 && !visited[i]){
                dfs(i);
            }
        }
    }
    
    for (let i=0; i < computers.length; i++) {
        if (!visited[i]) {
            dfs(i)
            answer++;
        }
    }
    
    return answer;
}

 

틀린 코드)

아무리 봐도 왜 틀렸는진 모르겠지만 1,2,4,7번 테케가 자꾸 틀린다...

function solution(n, computers) {
    // link 객체 만들기
    // dfs. 파라미터는 루트노드
    // 엣지케이스는 큐에 더 이상 컴퓨터가 없을 때
    // dfs 종료될 때 네트워크 개수 + 1
    let answer = 0;
    let link = {};
    let visited = new Array(n).fill(0);
    
    computers.map((el,idx) => link[idx] = []);
    
    for(let i=0;i<computers.length;i++){
        for(let j=0;j<computers.length;j++){
            if(j!==i && computers[i][j] === 1) link[i].push(j);
        }
    }
    
    const dfs = (root) => {
        let queue = [root];
        visited[root] = 1;
        
        while(queue.length){
            let cur = queue.shift();
            link[cur].map((el) => {
                if(!visited[el]) {
                    queue.push(el);
                    visited[el] = 1;
                }
            });
        }
    }
    
    for(let i=0;i<computers.length;i++){
        if(!visited[i]){
            dfs(visited[i]);
            answer++;
        }
    }
    
    return answer;
}

복기

3/31
4/14