문제 링크

프로그래머스 문제

풀이

문제를 보고 직관적으로 크게 어렵지 않게 아이디어를 떠올릴수 있는 문제였습니다.

다음과 같이 여러 노드들의 연관관계중, 덩어리 별로 그 개수를 파악하는 문제입니다.

dfs방식을 통해 현재 노드와 연결된 모든 노드를 완전탐색을 통해서 구해내는 방식을 고안하게 되었습니다.

DFS문제의 주의할점

1. dfs에서 매개변수로 담고 있는 상태에 주목할것
2. dfs의 함수 내부에서는 크게 두가지를 주목하여 작성해야 한다. 종료 조건과 다음 실행조건
3. 종료 조건의 경우 마무리 되는 경우와 dfs를 조기 종료시키는 조건을 추가해야 한다. dfs를 조기 종료시키는 조건의 경우 시간복잡도를 줄이는데 큰 기여를 한다.
4. 다음 실행조건 또한 마찬가지다. 잘못된 분기로 가지는 않는지, 혹은 모든 분기를 검사하는게 맞는지 확인하는데 중요한 역할을 수행한다.
5. 여기서 잘못된 분기라 함은 일반적으로 방문했던 node인경우가 있다. 이 경우 visited 배열을 통해서 확인하곤 한다.
6. 하지만 visited 배열을 dfs 함수 밖에서 선언한 경우 다른 분기에서 이 배열을 모두 공유한다. 이때 문제가 생길 가능성이 매우 높다.
7. 만약 분기별로 visted 상태를 다르게 보존해야 하는경우 매개변수에 visited 상태를 공유한다.

코드

function solution(n, computers) {
    var answer = 0;
    let visited = new Array(n).fill(false)
    
    const dfs = (curNode) => {
        //특별한 종료조건이 없다
        
        //다음 조건
        
        for(let i=0; i< n; i++){
            
                if(computers[curNode][i] === 1 && !visited[i]){
                    visited[i] = true;
                    dfs(i)
                }
                if(computers[i][curNode] === 1 && !visited[i]){
                    visited[i] = true;
                    dfs(i)
                }
            
        }
        
        
    }
    
    for(let i=0; i< n; i++){
        if(!visited[i]){
            visited[i] = true;
            dfs(i)
            answer++;
        }
        
    }
    
    return answer;
}