프로그래머스 네트워크

안녕 나 알고리즘 마스터 강경규
오늘 드디어 dfs를 활용하여 인접행렬을 탐색하는 문제를 풀었어~
스터디 발표에서 막히는 부분이 있어서 디버깅을 해서 이해해서 왔지

//풀이 설명은 여기서 해볼께요

function solution(n, computers) {
    const visited = Array.from({length : n}, ()=>false)
    /*	1
    컴퓨터의 개수만큼 false를 가진 배열을 만들어준다
    ex) 예시를 보면 모두 n이 3이기 때문에
    [false, false. false] 형태의 배열이 만들어지고
    각각 방문하기 전이라는 의미이다.
    */
    
    let cnt = 0
    /*	2
    각각 연결 된 컴퓨터들의 뭉치를 세어 줄 변수이다
    보시다시피 밑에서 dfs함수를 선언 해주었다
    */

    const dfs = (v) => {
        visited[v] = true
        //5 환영한다 v는 밑에서 가져온 i와 동일하다 기존에 방문을 하지 않았으니 바로 방문처리 해준다
        for(let j=0; j<computers[v].length; j++){
            if(computers[v][j] == 1 && visited[j] == false)
            dfs(j)
        }
      /*6
	최초로 들어오는 0번 인덱스를 예를 들어보겠다.
    여기서 의미하는 computer[v]는 computer[0]으로 치환이 되며 그 내부에는
    [1,1,0]이 있으므로 length는 3을 의미하겠다 모르겠으면 밑에 솔루션 함수 선언하는 부분을 봐줬으면 좋겠다
    그리고 그 안에 있는 하나하나의 요소에 접근하여 이 컴퓨터가 어떤 컴퓨터와 연결되어 있는지
    그리고 그 연결 된 컴퓨터가 이미 방문한 곳은 아닌지를 판별해내서 말 그대로 깊이 파고들 것이다.
    dfs의 의미는 알고 있길 바란다
    그렇게 반복하여 연결 된 모든 컴퓨터를 탐색하다 보면 언젠간 끝난다 그렇게 하면 밑에 반복문의 dfs가 종료되어 cnt++이 실행되는 것이다
      */
    }
    /*3
    해당 반복문의 역할은 n의 개수만큼 dfs를 실행해주는 것
    0번부터 실행이 될텐데 말로 풀어 설명해보자면
    0번 컴퓨터에 접근하여 연결되어 있는 모든 컴퓨터를 탐색해줄 것이다.
    그렇게 연결 된 모든 컴퓨터를 탐색하면 위 반복문을 빠져나오고 함수가 종료 되는데
    그렇게 나오면 연결 된 한 뭉치의 네트워크를 모두 탐색한 것 이므로 카운트++ !!
    */
    for(let i=0; i<n; i++){
        if(visited[i] == false){
          //4 방문을 한 컴퓨터인가 체크해주고 방문을 하지 않았다면 dfs를 실행! 카운트는 그 후에 늘어날 것
            dfs(i)
            cnt++
        }
      /*7
      이제 내 설명은 막바지에 다가왔다 모든 컴퓨터의 방문이 처리가 되었다면 
      위 반복문은 의미없이 방문 여부를 확인한다 
      그렇게 방문하지 않은곳은 방문하여 모든 인접 컴퓨터의 방문처리를 해줄 것이고,
      그렇게 각각 연결되어 있는 네트워크들이 모두 카운트가 된다
      내 설명이 이해가 안간다면 댓글을 남겨주어라
      디버깅을 하며 설명해드릴 수 있습니다.
      */
    }
    return cnt
}

console.log(solution(3,[[1, 1, 0], [1, 1, 0], [0, 0, 1]]))

먼저 문제에 대해 보자

• dfs를 활용해서 푼 이유는 단순히 모든 노드를 탐색해야 할 것 같았고 풀어본적이 없어서였어요
• 1은 해당 인덱스의 컴퓨터와의 연결 유무를 나타냅니다
• 그걸 이용하여 연결되어 있는 모든 컴퓨터에 접근하여 나누어져 있는지를 판별할겁니다.
• n(컴퓨터의 수)만큼 반복하는 for문 선언
  아 문제설명이구나 풀이설명아니구나 하하

//설명없는 깨끗한 코드임다!
function solution(n, computers) {
    const visited = Array.from({length : n}, ()=>false)
    let cnt = 0

    const dfs = (v) => {
        visited[v] = true
        
        for(let j=0; j<computers[v].length; j++){
            if(computers[v][j] == 1 && visited[j] == false)
            dfs(j)
        }
    }
    
    for(let i=0; i<n; i++){
        if(visited[i] == false){
            dfs(i)
            cnt++
        }
    }
    return cnt
}

console.log(solution(3,[[1, 1, 0], [1, 1, 0], [0, 0, 1]]))
console.log(solution(3, [[1, 1, 0], [1, 1, 1], [0, 1, 1]]))

디버깅과 설명 글을 적으며 한번 더 정리해보았다
3레벨짜리 문제인데 다른 문제에 비해 간단한 편인듯?..
for문을 적극 활용해야 한다는 힌트를 얻기 전에는 풀지 못했지만 ㅎ
아무트 즐거웠어요 안녕~