[프로그래머스/js] 네트워크 (Lv. 3)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43162

`프로그래머스 :: 네트워크 :: Lv. 3`

 

문제 리뷰

Lv. 3 문제를 블로그에 포스팅하는게 이번이 처음이네요. ^^ 기념적인 게시글 입니다. ㅋ

 

저는 문제 설명에 이렇게 생긴 그림이 있으면,

일단 graph로 만들어 버리고 싶은 충동이 듭니다.

graph로 만들어서 bfs든 dfs든 탐색하면 좋겠다는 생각이 마구 듭니다.

탐색하면서 문제 조건에 따라 이것저것 처리하고 정답을 return 하면 되겠다는 계획도 세우게 됩니다.

 

많은 분들께서 공감하실텐데요. (ㅋ?)

 

고민의 흔적 in 그림판

대략적인 설계는 위 이미지에서 확인하실 수 있습니다.

ㄴ 네?

ㄴ 뭘 어떻게 확인할 수 있는 건데요?

 

(코드로 확인해 봅시다)

 

첫 번째 시도 (정답)

code

function solution(n, computers) {
    let answer = 0;
    let graph = new Map();
    let needVisit = []; // stack
    let visited = new Array(n).fill(false);
    let focus = 0;
    
    // graph 구성
    computers.forEach((cur, idx) => {
        for (let i = 0; i < n; i++) {
            if (cur[i] === 1) {
                if (graph.get(idx)) {
                    graph.set(idx, [...graph.get(idx), i]);
                }
                else {
                    graph.set(idx, [i]);
                }
            }
        }
    });
    
    while (focus > -1) {
        needVisit.push(...graph.get(focus));
        
        while (needVisit.length > 0) {
            const target = needVisit.pop();
            if (!visited[target]) {
                needVisit.push(...graph.get(target));
                visited[target] = true;
            }
        }
        
        answer++;
        focus = visited.indexOf(false);
    }
    
    return answer;
}

review

먼저 graph로 만들어 준 뒤,

만들어 둔 graph에서 dfs로 탐색을 하게 되는데

이 탐색 과정에서 `needVisit` 라는 `stack`과 `visited`라는 체크 표를 이용한 모습입니다.

 

하나의 네트워크에서 가장 깊은 노드까지 탐색을 하게 된 이후에도

visited에 false가 남아있다면,

즉, 해당 네트워크에서 연결되어 있지 않기 때문에 아직 visit 하지 못 한 노드가 남아있다면,

걔들은 또 어떤 네트워크로 형성되어 있는지 확인해봐야 합니다.

 

그리고 새 네트워크를 확인할 때마다 answer++ 를 하게 되는 것이죠!!

 

잼있는 시간이었습니다.