예를 들어 1번과 2번을 연결지으려고 한다면?
indexArray
에 포함되어 있지 않다면 새로운 네트워크이므로 갯수추가.indexArray
에 포함되어 있다면 네트워크를 확장하는 것이므로 갯수 추가하지 않는다.indexArray
에 포함되어 있다면 이미 네트워크에 포함되어 있는 경로이므로 함수를 리턴.function solution(n, computers) {
let answer = 0;
let indexArray = [];
const func = (start, finish) => {
// 중복체크
const isStartInclude = indexArray.includes(start);
const isFinishInclude = indexArray.includes(finish);
if (isStartInclude && isFinishInclude) {
// 둘다 중복되는 것이면 함수 돌릴필요없다. ( 이미 네트워크에 포함되어있으니깐 )
return;
}
if (!isStartInclude && !isFinishInclude) {
// 둘다 처음등장하는거면 네트워크 추가!
answer++;
}
// 방문자 체크를 해준다.
indexArray.push(start, finish);
// 도착 인덱스에서 갈 수 있는 곳을 조사해서 호출한다.
for (let check1 = 0; check1 < computers[finish].length; check1++) {
// 자기자신이 아니면서 연결되어있는 곳은 호출한다.
if (finish !== check1 && computers[finish][check1] === 1) {
func(finish, check1);
}
}
};
for (let check = 0; check < computers.length; check++) {
if (computers[check].filter((item) => item === 1).length === 1) {
// 자기 자신 밖에 연결된게 없는 경우 네트워크 추가 !
answer++;
}
for (let check1 = 0; check1 < computers[check].length; check1++) {
// 자기자신이 아니면서 연결되어있는 경우 호출한다.
if (check !== check1 && computers[check][check1] === 1) {
func(check, check1);
}
}
}
return answer;
}
다음은 자기 자신만 연결되어 있는 경우의 처리가 func 내부에서 되지 않아 solution
메소드안에서 처리하는 모습이다.
for (let check = 0; check < computers.length; check++) {
if (computers[check].filter((item) => item === 1).length === 1) {
// 자기 자신 밖에 연결된게 없는 경우 네트워크 추가 !
answer++;
}
for (let check1 = 0; check1 < computers[check].length; check1++) {
if (check !== check1 && computers[check][check1] === 1) {
func(check, check1);
}
}
}
지저분한 모습이다
indexArray.includes()
부분includes()
메소드의 경우 인자로 들어오는 값이 배열 안에 있는지를 점검한 후 참, 불참 값을 리턴한다. 배열을 한 번 순회해야하므로 복잡도 커질 것임
let arr;
let visitArr;
function solution(n, computers) {
let ctr = 0;
arr = computers;
visitArr = new Array(n).fill(false);
for(let i in arr) {
ctr += dfs(i);
}
return ctr;
}
function dfs(i) {
if(visitArr[i] == true) return 0;
else visitArr[i] = true;
for(let j in arr[i]) {
if(arr[i][j] == 1)
dfs(j);
}
return 1;
}
자기 자신의 경로만 있는 경우 한 번도 등장하지 않았으므로 자연스럽게 처리
굳이 나처럼 시작점과 도착점의 등장 여부를 판단하지 않아도 됨
solution(4, [
[1, 1, 1, 0],
[1, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 1],
]);
다음의 경우 2-0에서 한 번더 1을 리턴하지 않도록 하기위해 시작점을 검사했었음 (본인)
허나 이 사람의 코드처럼 들어가서 시작점의 모든 경로 다 포문으로 돌려놓으면 자연스럽게 처리됨
let answer = 0;
const visited = [];
const dfs = function (idx) {
if (visited.includes(idx)) {
return 0;
} else {
visited.push(idx);
for (let check1 = 0; check1 < computers[idx].length; check1++) {
if (computers[idx][check1] === 1) {
dfs(check1);
}
}
return 1;
}
};
for (let check = 0; check < computers.length; check++) {
answer += dfs(check);
}
return answer;
solution(4, [
[1, 1, 1, 0],
[1, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 1],
]);
을 실행시키는 경우
dfs(0)start
-> dfs(0) return 0
-> dfs(1) -> dfs(0) return 0
-> dfs(1) return 0
-> dfs(3) -> dfs(1) return 0
-> dfs(3) return 0
-> dfs(2) -> dfs(0) return 0
-> dfs(2) return 0
-> return 1
dfs(1) -> dfs(0,1,3) 수행하지만 모두 중복 되어 리턴 0
dfs(2) -> dfs(0,2) 수행하지만 모두 중복되어 리턴 0
dfs(3) -> dfs(1,3) 수행하지만 모두 중복되어 리턴 0