[프로그래머스] (JavaScript) 네트워크 - DFS

[프로그래머스] (JavaScript) 네트워크 - DFS

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미한다.

예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어 있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있다.

 

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers 가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하자.

---

제한 사항

• 컴퓨터의 개수 n 은 1 이상 200 이하인 자연수
• 각 컴퓨터는 0부터 n - 1 인 정수로 표현
• i 번 컴퓨터와 j 번 컴퓨터가 연결되어 있으면, computers[i][j] 를 1로 표시
• computers[i][i] 는 항상 1

---

입출력 예

n	computers	return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1
5	[[1, 1, 0, 1, 0], [1, 1, 0, 0, 0], [0, 0, 1, 0, 1], [1, 0, 0, 1, 1], [0, 0, 1, 1, 1]]	1
6	[[1, 1, 0, 1, 0, 0], [1, 1, 0, 0, 0, 0], [0, 0, 1, 0, 1, 0], [1, 0, 0, 1, 0, 0], [0, 0, 1, 0, 1, 0], [0, 0, 0, 0, 0, 1]]	3

---

입출력 예 설명

[입출력 예 #1]

아래와 같이 2개의 네트워크가 있음

 

[입출력 예 #2]

아래와 같이 1개의 네트워크가 있음

 

[추가 - 입출력 예 #3]

[1, 2, 3, 4, 5] 가 연결된 1개의 네트워크가 있음

 

[추가 - 입출력 예 #4]

[1, 2, 4], [3, 5], [6] 이 연결된 3개의 네트워크가 있음

---

정답 코드

function solution(n, computers) {
    let answer = 0;
    const len = computers.length;
    const visited = new Array(len).fill(false)
    
    const dfs = (i) => {
        visited[i] = true;
        for (let j = 0; j < len; j++) {
            if (!visited[j] && computers[i][j] == 1) dfs(j);
        }        
    }
    for (let i = 0; i < len; i++) {
        if (!visited[i]) {
            dfs(i);
            answer++;
        }
    }
    return answer;
}

 

---

코드 풀이

let answer = 0;
const len = computers.length;
const visited = new Array(len).fill(false)

 

answer 변수와 len 상수를 생성하고, 네트워크 상에 연결된 컴퓨터의 방문 여부를 판단할 visited 배열을 생성해 준다.

 

const dfs = (i) => {
    visited[i] = true;
//  for (let j = 0; j < len; j++) {
//      if (!visited[j] && computers[i][j] == 1) dfs(j);
//  }        
}

 

dfs 함수는 인덱스 i 를 매개변수로 받고, i 번 컴퓨터를 방문처리 한다. 

 

for (let j = 0; j < len; j++) {
    if (!visited[j] && computers[i][j] == 1) dfs(j);
}

 

그리고 i 번 컴퓨터에서 연결된 j 번 컴퓨터를 찾는 for 문이 돈다.

 

이때, j 번 컴퓨터가 방문되지 않고, i 번 컴퓨터와 j 번 컴퓨터가 연결되어 있는지 확인하고, 연결되었으면 dfs(j) 를 호출하여 j 번 컴퓨터와 연결되어 있는 또 다른 컴퓨터를 찾는다.

 

이렇게 dfs 함수가 다 끝나면, 방문처리 된 컴퓨터들이 하나로 연결된 네트워크를 이루고 있다는 것을 알 수 있다.

 

for (let i = 0; i < len; i++) {
    if (!visited[i]) {
        dfs(i);
        answer++;
    }
}

 

하나로 연결된 네트워크를 찾았으니 answer++ 를 해준다.

 

i 가 증가된 다음 for 문으로 방문되지 않은 컴퓨터를 찾고, 모든 컴퓨터가 방문 처리가 된 후 for 문이 종료되어 총 합한 answer 값을 리턴한다.

---

풀이 상세

모든 방법을 탐색 하여 모든 컴퓨터가 방문 처리 된 후 최종 네트워크 개수를 구하는 것이므로 DFS으로 풀었다.

 

입출력 예시로 설명해 보겠다.

 

n : 6

computers

: [[1, 1, 0, 1, 0, 0], [1, 1, 0, 0, 0, 0], [0, 0, 1, 0, 1, 0], [1, 0, 0, 1, 0, 0], [0, 0, 1, 0, 1, 0], [0, 0, 0, 0, 0, 1]]

 

0번 컴퓨터와 1번 컴퓨터만 보면,

 

(f, f, f, f, f, f)

i = 0 → f [조건 O] → dfs(0)

    dfs(0) → (t, f, f, f, f, f)

    j = 0 → t (방문됨) [조건 X]

    j = 1 → f && [0][1] == 1 [조건 O] → dfs(1)

        dfs(1) → (t, t, f, f, f, f)

        j = 0 → t (방문됨) [조건 X]

        j = 1 → t (방문됨) [조건 X]

        j = 2 → f && [1][2] == 0 [조건 X]

        j = 3 → f && [1][3] == 1 [조건 O] → dfs(3)

            dfs(3) → (t, t, f, t, f, f)

             j = 0 → t (방문됨) [조건 X]

             j = 1 → t (방문됨) [조건 X]

             j = 2 → f && [3][2] == 0 [조건 X]

             j = 3 → t (방문됨) [조건 X]

             j = 4 → f && [3][4] == 0 [조건 X]

             j = 5 → f && [3][5] == 0 [조건 X]

        (t, t, f, t, f, f)

        j = 4 → f && [1][4] == 0 [조건 X]

        j = 5 → f && [1][5] == 0 [조건 X]

    (t, t, f, t, f, f)

    j = 2 → f && [0][2] == 0 [조건 X]

    j = 3 → t (방문됨) [조건 X]

    j = 4 → f && [0][4] == 0 [조건 X]

    j = 5 → f && [0][5] == 0 [조건 X]

(t, t, f, t, f, f)

i = 1 → t (방문됨) [조건 X]

(t, t, f, t, f, f)

i = 2 → f [조건 O] → dfs(2) ... 

 

i = 0일 때, [0번, 1번, 3번] 컴퓨터가 하나로 연결된 네트워크라는 것을 찾았다.

 

0번, 1번, 3번을 제외한 2번, 4번, 5번 컴퓨터는 방문 여부가 false 처리되어 있으므로 2번, 4번, 5번 컴퓨터로 나머지 네트워크의 개수를 찾으면 된다.