[프로그래머스 자바스크립트] ‘네트워크’ 풀어보기

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

 

---

1. 생각

DFS를 사용해서 풀어야 하는 문제다. 자바스크립트에서 DFS를 어떻게 풀어야되는지 아래의 블로그 글을 참고했다.

 

링크: https://chamdom.blog/dfs-using-js/

[알고리즘] JavaScript로 구현하는 DFS

 

문제에서 computers 배열을 제공하는데, 이 배열은 어떤 한 노드가 다른 노드와 연결되어 있으면 연결되있는 노드의 index에 1을, 연결되있지 않으면 그 노드의 index에 0을 작성해놓은 배열들로 구성된 배열이다.

예시) [[1, 1, 0], [1, 1, 1], [0, 1, 1]]

 

하지만 내가 필요한 배열은 어떤 한 노드가 어떤 노드와 연결되어있는지, 그 index가 담겨져있는 배열들의 모음이다.

예시) [[1],[0,2],[1]]

 

따라서 computers 배열을 순회하며 DFS에 필요한 배열을 생성하는 makeGraph 메서드를 만들었다.

 

그리고 DFS에 필요한 visited 배열을 만들고, 0번 노드부터 n-1번 노드까지 순회하며 DFS를 실행했다. visited[n]이 false면 n번 노드에 dfs가 실행되지 않았다는 뜻이므로(즉, 다른 네트워크라는 뜻이므로) answer에 1을 더 해주었다. 그리고 순회가 끝나면 더해진 answer를 return했다.

---

2. 코드

function solution(n, computers) {
    let answer = 0;
    const graph = makeGraph(computers);
    const visited = Array(n).fill(false);
    
    
    for(let i = 0; i < n; i++) {
        if(visited[i] === false) {
            answer++;
            dfs(graph, i, visited);
        }
    }
    
    return answer;
}

function makeGraph(graph) {
    const graphArray = [];
    
    for(let i = 0; i < graph.length; i++) {
        const array = [];
        for(let j = 0; j < graph[i].length; j++) {
            
            if(i !== j) {
                if(graph[i][j] === 1) {      
                    array.push(j);
                }
            }
        }
        
        graphArray.push(array);
    }
    
    return graphArray;
}

function dfs(graph, v, visited, answerArray) {
    visited[v] = true;
    
    
    for (let node of graph[v]) {
        if(!visited[node]) {
            dfs(graph, node, visited);
        }
    }
}