programmers - 깊이 우선 탐색 - 네트워크

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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입니다.

---

네트워크 연결상태를 보려면 주어진 A, B, C 모두를 방문해서 연결여부를
확인해줘야 한다. 주어진 computers 배열을 3 x 3 이차원 인접행렬 꼴로 생각하고 접근한다.

function solution(n, computers) {
    let answer = 0;
    let check = Array(computers.length).fill(0);
        
    for(let i = 0;  i < computers.length; i++ ){
        if(!check[i]){
            DFS(i);
            answer+=1;
        }
    }
    
    function DFS(index){
        check[index] = 1;
        
        for(let i = 0; i< computers.length; i++ ){
            if(computers[index][i] === 1 && !check[i]){
                DFS(i);
            }
        }
    }
        
    return answer;
}

1) 각 노드에 대한 방문여부를 check 배열을 사용해 점검한다.
방문되지 않은 상태를 0, 방문한 상태를 1로 가정. 따라서 초기 값은 0으로 설정.

2) 첫 번째 노드부터 출발
check[0] = 0이기 때문에 if문 안의 DFS가 실행되고 check = 1로 할당

3) DFS가 호출 되고 computers[index][i] === 1 && !check[i]를 비교하게 되는데 두 노드 사이가 연결되어 있고 방문하려는 노드가 비어 있을 때 DFS함수를 다시 순환호출 한다.

4) DFS 안에서 answer를 증가시키지 않고 자기 자신을 순환 호출하는 이유는
서로 연결되어 있는 같은 네트워크이기 때문이다. answer는 네트워크의 수를 카운트하는 기능의 변수.

def solution(n, computers):
    answer = 0
    check = list(0 for i in range(len(computers)))
            
    def DFS(index):
        check[index] = 1
        
        for i in range(len(computers)):
            if computers[index][i] == 1 and (check[i] == 0):
                DFS(i)
    
    for i in range(len(computers)):
        if check[i] == 0:
            DFS(i)
            answer += 1
    
    return answer