프로그래머스 - 네트워크

1. 문제

문제 링크

설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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로 표현합니다.
• computer[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

2. 풀이

DFS와 BFS의 완전 기본기를 물어보는 문제입니다.
computers 인자는 인접 리스트 형태로 들어오게 되고
우리는 그 정보를 통해 컴퓨터를 순회하여 연결 그래프가 몇 개인지 카운트하면 됩니다.
저는 DFS를 이용해 순회해보겠습니다.

계획1 - DFS를 이용해 순회하는 함수를 만듭니다.

const link = (c) => {
    // 현재 c 방문 표시
    visit[c] = 1;

    for (let j = 0; j < n; j++) {
        // 자기 자신일 땐 넘어가기
        if (c == j) continue;
      
	// 방문하지 않았고, 현재 c와 j가 연결됐다면 j부터 다시 순회
        !visit[j] && computers[c][j] && link(j);
    }
};

문제의 두 번째 예제로 시뮬레이션을 해보면 다음과 같이 됩니다.

link(1)이 호출해서 visit[1] = 1을 표시하고 재귀적으로 link(2)를 호출합니다.

link(2)는 visit[2] = 1을 표시하고 재귀적으로 link(3)을 호출합니다.
link(3)은 visit[3] = 1을 표시하고 더 이상 순회할 곳이 남아있지 않아 종료됩니다.

3. 전체 코드

function solution(n, computers) {
    const visit = [...Array(n)].map(() => 0);
    let ans = 0;

    const link = (c) => {
        visit[c] = 1;

        for (let j = 0; j < n; j++) {
            if (c == j) continue;

            !visit[j] && computers[c][j] && link(j);
        }
    };

    for (let i = 0; i < n; i++) {
        if (visit[i]) continue;

        link(i);
        ans++;
    }

    return ans;
}