프로그래머스 - 네트워크

<문제>

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

 

<문제 핵심>

1. dfs를 활용한 문제

 

2. 해당 인덱스를 방문을 했는지 안 했는지 체크 해줌으로써 무한 루프 방지 해주기

-> visited 배열 생성

 

3. computers 배열을 순회하면서 컴퓨터와 연결된 컴퓨터를 발견하고 방문하지 않은 컴퓨터라면 다시 재귀적으로 다음 컴퓨터를 기준으로 탐색

 

<문제 풀이과정 및 순서도>

1. n개 만큼 방문처리 배열을 생성한다.

let visited = Array(n).fill(false);
let answer = 0;

 

2. computes배열 갯수만큼 반복문을 돌리고 방문하지 않은 컴퓨터라면 dfs함수를 호출한다.

for (let i=0; i < computers.length; i++) {
    if (!visited[i]) {
        dfs(i)
        answer++;
    }
}

 

3. i 컴퓨터와 연결된 컴퓨터 j가 있고 j번째 컴퓨터를 방문하지 않았다면 j를 기점으로 다시 dfs함수를 호출한다.

function dfs(i) {
    visited[i] = true;
    for(let j=0; j<computers[i].length; j++) {
        if(computers[i][j]===1 && !visited[j]){
            dfs(j);
        }
    }
}

 

<전체 코드>

function solution(n, computers) {
    //n개의 갯수만큼 방문체크 배열 세팅
    let visited = Array(n).fill(false);
    let answer = 0;

    function dfs(i) {
        visited[i] = true;
        for(let j=0; j<computers[i].length; j++) {
            if(computers[i][j]===1 && !visited[j]){
                dfs(j);
            }
        }
    }
    
    for (let i=0; i < computers.length; i++) {
        if (!visited[i]) {
            dfs(i)
            answer++;
        }
    }
    return answer;
}

 

<전체 코드 - bfs 방식으로도 풀어 본 문제>

function solution(n, computers) {
    let visited = Array(n).fill(false);
    let answer = 0;

    function bfs(start) {
        let queue = [start];
        visited[start] = true;

        while (queue.length > 0) {
            let node = queue.shift();

            for (let j = 0; j < computers[node].length; j++) {
                if (computers[node][j] === 1 && !visited[j]) {
                    visited[j] = true;
                    queue.push(j);
                }
            }
        }
    }

    for (let i = 0; i < computers.length; i++) {
        if (!visited[i]) {
            bfs(i);
            answer++;
        }
    }
    
    return answer;
}