(Python) - 프로그래머스 : 네트워크

https://programmers.co.kr/learn/courses/30/lessons/43162

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

 

• 해설 : 컴퓨터의 개수 n과 컴퓨터 사이의 연결관계인 computers배열이 주어질 때,  컴퓨터들 사이에 몇 개에 독립적인 그래프가 있는지 찾는 문제이다. 

 

 

 

• 풀이 :

BFS 또는 DFS로 구현할 수 있는 문제이다. 그래프의 탐색을 구현할 수 있는지 묻는 문제인데 나는 BFS로 풀었다. 우선, 노드 사이의 연결관계인 computers 배열에서 탐색하지 않은 노드 1개를 꺼내서 bfs로 인접한 노드들을 모두 탐색하고  c 배열을 통해 탐색 완료 확인을 해주었다. 그리고 answer을 1증가시켜 주었고 모든 노드가 탐색완료 상태가 될 때 까지 실행하였다.

 

 

 

 

from collections import deque
 
def solution(n, computers):
    answer = 0
    c = [0 for _ in range(n)]
    for i in range(n):
        if c[i] == 0:
            queue = deque()
            queue.append(i)
            c[i] = 1
            while queue:
                x = queue.popleft()
                for j in range(n):
                    if c[j] == 0:
                        if computers[x][j] == 1 and i != j:
                            queue.append(j)
                            c[j]=1
            answer += 1
    return answer