- Published on
프로그래머스 네트워크 (bfs/dfs)
- Authors
- Name
- Deokgoo Kim
문제 풀이
bfs/dfs 분류의 문제입니다. 코멘트에서도 언급하지만
테스트케이스에 비대칭으로 주어지는것 같습니다.
난이도는 낮다고 생각합니다.
function solution(n, computers) {
let answer = 0;
let networkMap = new Array(n);
// 주어진 computers를 대칭적으로 만듭니다.
for(let y=0;y<n;y++) {
for(let x=0;x<n;x++) {
if(computers[y][x] || computers[x][y]) {
computers[y][x] = 1;
computers[x][y] = 1;
}
}
}
const dfs = (target) => {
networkMap[target] = 1;
for(let z=0;z<n;z++) {
if(target === z) continue;
if(computers[target][z] && !networkMap[z]) {
dfs(z);
}
}
}
for(let i=0;i<n;i++) {
if(networkMap[i]) continue;
answer++;
dfs(i);
}
return answer;
}