문제

https://programmers.co.kr/learn/courses/30/lessons/43162
a, b, c, d라는 컴퓨터가 있고 a -> b, b -> c, d 이렇게 연결돼 있다고 하면
현재 네트워크는 a -> b -> c 연결 한개와 d 혼자 있는 네트워크 두개가 있다.
이렇게 네트워크 수가 몇개인지 구하는 문제이다.

입력: [n, computers]

• n: 1 이상 200 이하의 자연수
  • 각 컴퓨터는 n-1인 정수로 표현한다.
• computers: 길이가 n인 2차원 배열
  • i컴퓨터와 j컴퓨터가 연결돼있다면 computers[i][j]는 1이다.
  • computers[i][i]는 항상 1이다.

출력: 네트워크의 갯수 출력.

문제 접근

우선 그래프를 그려서 어떤식으로 탐색할지 생각해봤다.

위의 그래프의 computers 배열은 이렇게 돼있을것이다.

const computers = [
  // 1, 2, 3, 4, 5, 6, 7 번째 노드
	[1, 1, 1, 0, 0, 0, 0],
  	[1, 1, 0, 1, 0, 0, 0],
  	[1, 0, 1, 0, 0, 0, 0],
  	[0, 1, 0, 1, 0, 0, 0],
  	[0, 0, 0, 0, 1, 1, 0],
  	[0, 0, 0, 0, 1, 1, 0],
  	[0, 0, 0, 0, 0, 0, 0]
];

만약 dfs를 사용해 끝까지 탐색한다고 하면 1 -> 2 -> 4 -> 3, 5 -> 6, 7
이런식으로 dfs의 첫부분이 세번 반복되고, 정답은 3이 될것이다.

그래서 for문으로 1~n번째 노드까지 dfs문을 시작하는데, 방문하지 않은 노드만 방문하도록 했다.
그러기 위해서 visited 변수를 추가로 선언해줬다.

const visited = [];

이제 방문한적 없으며, computers배열에서 1인 노드만 탐색하면 해결될거라 생각했다.
그리고 그 방법은 맞았다.

전체코드

function solution(n, computers) {
    const visited = [];
    let answer = 0;

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

위의 생각을 토대로 dfs 함수를 구현했다.

1. 방문하지 않은 노드만 탐색을 한다
2. computers[i][j] === 1인 노드만 탐색을 한다.