프로그래머스[JS] > 네트워크

🔥문제링크

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

프로그래머스

 

🔥풀이 핵심

제목 옆에도 표시 되었듯이 풀이의 핵심은 DFS 로 연결된 모든 컴퓨터들을 다 타고 들어가 하나의 네트워크 그룹으로 묶는 동시 들렀던 컴퓨터는 체크하여 해당 컴퓨터는 다시 들리지 않는 것 이다.  

 

🔥첫번째 내 풀이

내가 처음에 생각한 내풀이는 재귀함수를 사용하진 않았다. 하지만 재귀함수의 동작을 큐(queue)와 while을 통해 구현하였다. 아래와 같은 코드로 문제를 풀고 다른 사람들의 정답 코드를 참고하여 재귀함수를 이용하여 다시 풀어 보았는데 그 코드는 두번째 풀이에서 확인할 수 있다.

 

 

function solution(n, computers) {
    let networks = []
    let visited = Array(n).fill(0)
    
    for(let i=0; i<=n-1; ++i){
        // 안들렸으면 들린다.
        if(!visited[i]){
            let toVisit = [i]
            let group = [i]
            while(toVisit.length){
                let pick = toVisit.shift()
                visited[pick] = 1
                computers[pick].forEach((state,com_idx)=>{
                    if(state===1 && !group.includes(com_idx)){
                        toVisit.push(com_idx)
                        group.push(com_idx)
                    }
                })
            }
            networks.push(group)
        }   
    }
    return networks.length
    
}

 

🔥재귀함수를 이용한 다른 풀이

재귀로 푼 풀이가 코드가 조금 더 짧은 것 같긴하다. 재귀로 풀든 풀지 않든 중요한것은 아니다. 가장 중요한 것은 하나의 네트워크를 형성하는 컴퓨터들을 한번에 체크해야 하고 이를 참고해서 풀이를 진행해야 한다는 것이다. 

 

function solution(n, computers) {
    let answer = 0
    let visited = Array(n).fill(0)
    
    const dfs =(com_index)=>{
        if(visited[com_index]){
            return 0
        }
        
        visited[com_index] = 1 // 들렀다고 표기
        computers[com_index].forEach((isConnected,i)=>{
            // 연결되었으면
            if(isConnected){
                dfs(i)
            }
        })        
        return 1
    }

    for(let i=0; i<=n-1; i++){
        answer+=dfs(i)    
    }
    
    return answer
}