[프로그래머스/JavaScript] 네트워크 (Feat. DFS, 조금씩 이해된다...)

 

📊 1. 나만의 테스트 케이스 만들기 (많을수록 좋음)

아래와 같이 연결된 네트워크가 있다고 가정해봅시다.

          0
         /
  1 ----/------- 4
   \   /
    \ /
     2       3

 

테스트 케이스
n = 5
computers = [[1, 0, 1, 0, 0], [0, 1, 1, 0, 1], [1, 1, 1, 0, 0], [0, 0, 0, 1, 0], [0, 1, 0, 0, 1]]

 

그래프의 형태로 나타내면 아래와 같을 것 같군요. (연결 상태 확인하기)

0 : [2]
1 : [2, 4]
2 : [0, 1]
3 : []
4 : [1]

 

이 경우에는 "0, 1, 2, 4"와 "3"가 개별 네트워크로 연결되어, return(결과값)은 2여야 합니다.

 

🤔 2. 사고하기

(1) 0을 확인한다. (0)
(2) 0에 연결된 아이는 2이다. 2를 확인한다. (0 → 2)
(3) 2에 연결된 아이는 0, 1이다. 0은 이전에 확인했으므로, 1을 확인한다. (0 → 2 → 1)
(4) 1에 연결된 아이는 2, 4이다. 2는 이전에 확인했으므로, 4를 확인한다. (0 → 2 → 1 → 4)
(5) 4에 연결된 아이는 1이다. 1은 이전에 확인했으며, 더이상 연결된 아이가 없으므로 종료한다. (0 → 2 → 1 → 4)
(6) 3은 누구와도 연결되지 않았으므로 독립적인 네트워크 하나로 count 한다. (3)

즉, "0, 2, 1, 4"와 "3"이 개별 네트워크이므로, 결과 값은 2이다.

 

여기서 중요한 것은 바로, "이전에 확인했는가" 입니다. 중요한 내용이니, 다시 한 번 반복하겠습니다.

 

 

해당하는 값을 이전에 지나갔는지 (확인했는지, 다녀왔는지, 거쳐갔는지)를 구분하는 것이 가장 중요하다.

 

 

🧹 3. 로직 정리하기

vist = [false, false, false, false, false]

(1) visit[0] = false
     index = 0일 때, visit[0] = true로 만들기
     computers[0] = [1, 0, 1, 0, 0] 일 때, visit = false && 나와 연결되었는지 (1인지) → 2

     index = 2일 때, visit[2] = true로 만들기
     computers[2] = [1, 1, 1, 0, 0] 일 때, visit = false && 나와 연결되었는지 (1인지) → 1
     
     index = 1일 때, visit[1] = true로 만들기
     computers[1] = [0, 1, 1, 0, 1] 일 때, visit = false && 나와 연결되었는지 (1인지) → 4

     index = 4일 때, visit[4] = true로 만들기
     computers[4] = [0, 1, 0, 0, 1] 일 때, visit = false && 나와 연결되었는지 (1인지) → 없음 (종료)

(2) visit[1] = true → 넘어감, visit[2] = true → 넘어감

(3) visit[3] = false
     index = 3일 때, visit[3] = true로 만들기
     computers[3] = [0, 0, 0, 1, 0] 일 때, visit = false && 나와 연결되었는지 (1인지) → 없음 (종료)

(4) visit[4] = true → 넘어감


따라서 (1)와 (3)일 때, 네트워크의 개수를 1씩 증가시키면 된다.

즉, 이 문제에서 DFS는 해당하는 인덱스를 방문했는지 안했는지를 나타내는 함수로서 사용하면 된다.

 

⭐️ 4. 최종 결과

function solution(n, computers) {
    // 네트워크 수 세기
    let networks = 0;

    // 방문 여부 확인하기
    let visit = Array(n).fill(false);
    
    // 방문한 곳인지 확인 및 네트워크 수 증가시키기
    for (let i = 0; i < n; i++) {
        if (!visit[i]) {
            networks ++;
            isVisit(i);
        }
    }
    
    // DFS를 통해 방문한 곳인지 확인하는 함수
    function isVisit(index) {
        visit[index] = true;
        
        const computer = computers[index];
        
        for (let i = 0; i < computer.length; i++) {
            const isConnect = computer[i] === 1 ? true : false;
            
            // 방문하지 않았고 && 연결된 곳인지 확인
            if (!visit[i] && isConnect) {
                isVisit(i);
            }
        }        
    }
    
    return networks;
}

 

문제를 풀어나갈수록 DFS가 조금씩 이해되는 것 같습니다.

정말 많이 배운 문제이며, 앞으로도 꾸준히 해보도록 하겠습니다 :) 😆