프로그래머스 네트워크 JavaScript
2023년 2월 8일
문제 풀이
매개변수 컴퓨터들의 네트워크의 개수를 구하는 문제다. dfs를 이용해 컴퓨터들을 그룹화시켜 그룹 수(= 네트워크의 개수)를 리턴computerGroup = 컴퓨터의 그룹을 나타내는 배열로, 초기에 컴퓨터의 수만큼 -1로 채워 배열을 만든다. computerGroup[i] = -1은 i 컴퓨터가 어떤 그룹에도 속하지 않다는 것을 뜻한다. 이후 computerGroup[i] = -1 인 i 컴퓨터를 dfs 한다.
dfs의 재귀 조건은
- 자기 자신을 제외해야 하므로
i !== comIndex - 컴퓨터 간의 연결이 되어있어야 하기에
computers[comIndex][i] === 1 - 연결할 컴퓨터가 어떤 그룹에도 속하지 않아야 하기에
computerGroup[i] === -1이다.
solution.js
function solution(n, computers) {
let cnt = 0;
const computerGroup = new Array(n).fill(-1);
const dfs = (comIndex, groupIndex) => {
for (let i = 0; i < n; i++) {
if (i !== comIndex && computers[comIndex][i] === 1 && computerGroup[i] === -1) {
computerGroup[i] = groupIndex;
dfs(i,groupIndex);
}
}
};
for (let i = 0; i < n; i++) {
if (computerGroup[i] === -1) {
computerGroup[i] = cnt;
dfs(i, cnt++);
}
}
return cnt;
}