[Lv.3 / 프로그래머스 / 파이썬] 네트워크

 

 

 

 

프로그래머스

 

 

 

 

풀이

 

DFS 혹은 BFS를 사용해 네트워크의 개수를 찾는 문제이다.

주어진 정보로 각 노드에 대한 간선 정보를 담은 link 배열을 생성하고 모든 정점을 순회하며 방문 체크를 한다.

모든 방문 체크를 끝내기 위해 몇 번의 bfs가 필요한지 계산하여 반환하면 된다.

 

from collections import deque

def solution(n, computers):
    visited = [False] * n
    link = [[] for _ in range(n)]
    ans = 0
    
    for i in range(n):
        for j in range(n):
            # 연결이 되지 않았거나 자기 자신인 경우
            if not computers[i][j] or i == j:
                continue
                
            # 경로 추가
            link[i].append(j)
    
    # 모든 정점 순회
    for i in range(n):
        # 이미 방문한 정점
        if visited[i]:
            continue
        
        ans += 1
        q = deque([i])
        visited[i] = True
        
        while q:
            v = q.popleft()
            for w in link[v]:
                # 이미 방문한 정점
                if visited[w]:
                    continue
                
                visited[w] = True
                q.append(w)
    
    return ans