네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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입니다.
입출력 예ncomputersreturn
3
[[1, 1, 0], [1, 1, 0], [0, 0, 1]]
2
3
[[1, 1, 0], [1, 1, 1], [0, 1, 1]]
1
입출력 예 설명
예제 #1 아래와 같이 2개의 네트워크가 있습니다.
예제 #2 아래와 같이 1개의 네트워크가 있습니다.
나의 풀이
function solution(n, computers) {
const visited = Array(n).fill(false); // 방문 배열 초기화
let count = 0;
for (let i = 0; i < n; i++) {
if (!visited[i]) {
DFS(i);
// DFS가 종료되면 이곳으로 되돌아오게 되고,
// 더 이상 순회할 노드가 없으며, 하나로 연결된 네트워크는 모두 순회했음을 의미함
count++;
}
}
function DFS(c) {
visited[c] = true;
for (let i = 0; i < n; i++) {
// 방문하지 않은 노드이면서, c와 i가 연결되어있으면 DFS 함수 재귀호출
if (!visited[i] && computers[c][i]) DFS(i);
}
return;
}
return count;
}
DFS(깊이 우선 탐색)으로 문제를 해결했다.
DFS 강의를 들으면서 비슷한 문제를 JAVA로 풀었어서 접근 방식을 떠오르는데 오래걸리지 않았다.
DFS를 할 때는 항상 방문배열을 모두 false로 초기화해주는 작업이 필요하다.
count 변수는 네트워크의 갯수를 뜻하며 이 값이 최종 리턴되는 정답이다.
컴퓨터의 갯수만큼 for문을 돌면서, 해당 컴퓨터(노드)가 아직 방문하지 않은 곳이면, DFS를 호출한다.
DFS의 c는 파라미터로 들어온 값이며, visited를 true로 변경하여 방문한 노드임을 저장한다.
DFS 내부에서 또 다시 n만큼 for문을 돌면서,
i번째 방문 배열이 false이면서, i번째 컴퓨터가 해당 DFS의 파라미터로 들어온 컴퓨터와 연결되어있다면 (computer[c][i] = 1) DFS의 파라미터로 i를 넘겨 재귀호출한다.
