[프로그래머스] 네트워크 - Javascript (Lv.3)

📖 문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

 

✔️ 제한조건

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

n	computers	return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

 

💻 나의 코드

function solution(n, computers) {
    let networkCnt = 0;
    const visited = new Array(n).fill(0); // 방문여부를 표시할 visited변수를 n만큼 0으로 초기화 (0 : 방문 안 함, 1 : 방문함)
    
    // n만큼 반복 (computers의 길이 == 노드의 개수 만큼 반복)
    for(let i=0; i<n; i++){
        if(visited[i] === 0){ // 방문하지 않은 노드라면
            visited[i] = 1;   // 방문표시를 해준다
            networkDep(visited, computers, n, i); // neworkDep함수를 호출한다
            networkCnt++; // answer에 1을 더한다 (1을 더하는 이유는 newworkDep를 수행하고 네트워크의 개수가 하나 늘었다는 걸 표시하기 위해서다)
        }
    }
    return networkCnt; // answer를 return한다
}

// 깊이 탐색 함수
function networkDep(visited, computers, n, idx){
    visited[idx] = 1; // 받은 인덱스의 노드에 방문 표시를 한다
    
    // 0부터 n전까지 반복을 수행한다
    for(let i=0; i<n; i++){
        // 네트워크가 연결이 되어있고, 방문하지 않았다면 재귀호출을 수행한다
        if(computers[idx][i] === 1 && visited[i] === 0){
            networkDep(visited, computers, n, i);
        }
    }
}

 

🎤 코드 설명

접근방법 : 하나의 컴퓨터를 노드라 생각해야한다. 노드에 연결된 노드가 있을 때까지 계속 깊이 탐색 기법으로 탐색하면 네트워크의 개수를 구할 수 있다.

 

아래 설명에서 두 단어를 혼용했습니다. '컴퓨터 == 노드'

 

solution함수 (main함수)

• 네트워크의 개수를 셀 networkCnt변수를 0으로 초기화합니다.
• 컴퓨터(노드)의 방문 여부를 표시할 배열 변수 visited를 길이 n만큼 0으로 채웁니다. (0은 방문하지 않음, 1은 방문함을 의미합니다. )
• n만큼 반복을 수행합니다. (n의 computers.length와 같습니다.)
  • 방문하지 않는 노드라면
    • visited배열에 방문표시를 해줍니다. 
    • 현재 노드와 연결된 노드가 있는지 확인하고 있다면 깊이 탐색을 하기 위해 networkDep함수를 호출합니다. 이때 visited, computers, n, i가 전달됩니다. visited는 방문 여부를 표시하는 변수를 networkDep에서도 사용할 수 있기에 전달하고, computers는 노드 사이의 연결을 나타내는 배열이기에 반드시 필요합니다. n은 반복문 구현시 편하라고 전달하고, i는 현재 노드의 인덱스를 전달하는 것입니다.
    • 재귀 호출이 마무리되면 networkCnt에 1을 더합니다.
• networkCnt를 return합니다. 

networkDep함수 (깊이 탐색 함수)

• 전달받은 i값을 담은 idx인덱스를 방문처리 해줍니다.
• n만큼 반복을 수행합니다. 
  • 컴퓨터가 어떤 컴퓨터와 연결이 되어 있고, 방문하지 않았다면 재귀호출을 수행합니다. 

 

📜 채점 결과

정확성: 100.0

합계: 100.0 / 100.0

 

💬 배운 것

• 다른 블로그를 참고하고 코드를 작성했습니다. 코드를 보면 이해가 되지만 제가 직접 dfs로 활용을 할 수 없단 점이 문제입니다. 보완하기 위해 난이도가 낮은 dfs문제부터 차근차근 풀어봐야겠습니다. 
• solution함수의 for문 안에서는 방문하지 않은 노드일때만 networkDep함수를 호출합니다. networkDep함수는 재귀로 이루어져 있습니다. networkDep가 여러 번 재귀된다는 것은 그만큼 연결된 컴퓨터(노드)들이 많다는 의미입니다. 그럼 자연스럽게 solution함수안의 for문 안에 있는 if문에 적은 수행이 이루어지고 answer는 적게 증가합니다. answer가 적단 것은 그만큼 컴퓨터(노드)들이 많이 연결되어 있다는 뜻입니다. 

 

 

코딩테스트 연습 - 네트워크