[프로그래머스 / python / Level 3] 네트워크

문제

 

그래프 기초 문제로써, "연결 성분"의 개수를 구하는 문제이다. 즉 연결되지 않은 그래프의 개수를 구하면 된다. 크게 어렵지 않은 문제였다.

 

from collections import deque

def solution(n, computers):
    
    table = [[] for _ in range(n)]
    
    # 인접리스트 형태 변경
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
                
            if computers[i][j] == 1:
                table[i].append(j)
    
    visited = [False] * n
    
    # BFS 함수        
    def bfs(start):
        
        queue = deque([])
        queue.append(start)
        
        while queue:
            
            node = queue.popleft()
            visited[node] = True
            
            for next in table[node]:
                if not visited[next]:
                    queue.append(next)
    
    # 메인 로직
    result = 0
    for i in range(n):
        if not visited[i]:
            bfs(i)
            result += 1
    
    return result

 

나는 BFS로 해결했다. 입력받은 computers는 인접 행렬 형태이지만, 내가 사용하기 편한 인접 리스트 형태로 바꿨다.

 

BFS 알고리즘와 deque를 이용해 특정 노드를 시작으로 방문하게 되면, 하나의 그래프, 즉 연결된 노드에만 방문하게 된다.

메인 로직에서 모든 노드를 대상으로 BFS를 시도하되, 방문하지 않은 노드를 시작점으로 한다.

 

만약 모든 노드가 연결되어 있다면 BFS는 한 번만 실행될 것이고, 여러개로 나누어져 있다면 연결 성분의 개수만큼 BFS가 실행될 것이다. BFS가 실행될 때마다 result를 1씩 더해주고, 마지막으로 출력해주면 된다.