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

2025. 1. 27. 17:34·Algorithm/Programmers(JavaScript)

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

 

프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

 


1. 생각

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

 

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

 

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

dfs에 대해 알아보기 전에 우선 그래프에 대한 이해가 필요하다. 그래프에 대한 설명은 여기 에 자세히 정리해두었다. DFS란? DFS(Depth-First-Search) 는 …

chamdom.blog

 

문제에서 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);
        }
    }
}
저작자표시 비영리 변경금지 (새창열림)

'Algorithm > Programmers(JavaScript)' 카테고리의 다른 글

[프로그래머스 자바스크립트] ‘다리를 지나는 트럭’ 풀기  (1) 2025.03.03
[프로그래머스 자바스크립트] ‘베스트앨범’ 풀어보기  (1) 2025.02.02
[프로그래머스 자바스크립트] ‘정수 삼각형’ 풀어보기  (0) 2025.01.24
[프로그래머스 자바스크립트] ‘가장 큰 수’ 풀어보기  (0) 2025.01.20
[프로그래머스 자바스크립트] ‘모의고사’ 풀어보기  (0) 2025.01.11
'Algorithm/Programmers(JavaScript)' 카테고리의 다른 글
  • [프로그래머스 자바스크립트] ‘다리를 지나는 트럭’ 풀기
  • [프로그래머스 자바스크립트] ‘베스트앨범’ 풀어보기
  • [프로그래머스 자바스크립트] ‘정수 삼각형’ 풀어보기
  • [프로그래머스 자바스크립트] ‘가장 큰 수’ 풀어보기
퀵차분
퀵차분
웹 프론트엔드 개발자를 꿈꾸고 있습니다 :)
  • 퀵차분
    QC's Devlog
    퀵차분
  • 전체
    오늘
    어제
    • 분류 전체보기 (165)
      • Frontend (28)
        • HTML, CSS (7)
        • Javascript (3)
        • React (11)
        • Typescript (2)
        • Next.js (4)
      • Node.js (3)
      • Study (40)
        • Modern JS Deep Dive (13)
        • SQL (1)
        • Network (1)
        • 프롬프트 엔지니어링 (4)
        • 인공지능 (9)
        • 시스템프로그래밍 (11)
        • 선형대수학 (1)
      • Intern (4)
      • KUIT (20)
      • Algorithm (48)
        • Baekjoon(C++) (26)
        • Programmers(JavaScript) (22)
      • 우아한테크코스(프리코스) (4)
      • Project (7)
        • PROlog (4)
        • Nomadcoder (2)
      • 생각 (4)
      • Event (7)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    리액트
    HTML
    typescript
    KUIT
    자바스크립트
    프로그래머스 자바스크립트
    오블완
    next.js
    타입스크립트
    프로그래머스
    알고리즘
    티스토리챌린지
    음악추천
    시스템프로그래밍
    프론트엔드
    프롬프트 엔지니어링
    인공지능
    react
    javascript
    백준
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
퀵차분
[프로그래머스 자바스크립트] ‘네트워크’ 풀어보기
상단으로

티스토리툴바