프로그래머스 코딩테스트 고득점 Kit_DFS/BFS_네트워크

문제 보러 가기 👈 클릭!

💡 풀이

✔ 풀이 방법

입력으로 주어지는 computers을 그래프 구조로 생각하고, 이미 갔던 길은 연결을 끊어 다시 가지 않는 방식으로 DFS 순회한다.

총 네트워크 개수의 초기값을 n(컴퓨터 개수)으로 선언하고, 한 brunch에 연결되어있는 node의 개수를 뺀 후, 1(네트워크 1개)을 더한다.

구현 코드👇

def solution(n, computers):
    network_cnt = n #네트워크 개수의 초기값

    for start_v in range(n): 
        #dfs
        visited = [] #하나의 brunch에 연결 되어 있는 node
        stack  = [start_v]
        while stack:
            node = stack.pop()
            if node not in visited:
                visited.append(node)
                for i in range(n):
                    if node != i and computers[node][i]:
                        stack.append(i)
                        computers[node][i] = 0 #이미 지나온 길은 0으로 만듬
                        computers[i][node] = 0
                        
        if len(visited) != 1: #시작노드 말고 다른 노드를 방문한 경우
            #한 네트워크로 연결 된 컴퓨터 개수를 빼고 1을 더함
            network_cnt += (-len(visited) + 1) 
            
    return network_cnt