[프로그래머스] 네트워크 (BFS/너비우선탐색/python/파이썬)

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다.

예를 들어, 컴퓨터 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입니다.

입출력 예

n	computer	return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

아래와 같이 2개의 네트워크가 있습니다.

출처 :프로그래머스

예제 #2
아래와 같이 1개의 네트워크가 있습니다.

출처 :프로그래머스

 

<문제 풀이>

BFS 너비 우선 탐색

저는 이 문제를 BFS 너비 우선 탐색을 사용하여 풀었습니다.

입력으로 노드가 서로 연결되어 있다면 그 노드를 자식으로 가지는 그래프를 만들어줍니다.

그리고 그 그래프를 너비 우선 탐색하면서 네트워크 개수를 세어 줍니다.

 

 

 

<그래프 생성>

입력 형식은 다음과 같습니다.

문제에서 'i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers [i][j]를 1로 표현'이 의미하는 것은

 

예제 2  [[1, 1, 0], [1, 1, 1], [0, 1, 1]]라는 이중 리스트가 있다면

각 리스트의 인덱스는 연결 시작 노드이고

그 안의 첫 번째 리스트의  각 요소는 해당 컴퓨터와의 연결 유무입니다.

0번 컴퓨터는 0번과 연결 O/1번과 연결 O/2번과 연결 X

1번 컴퓨터는 0번과 연결 O/1번과 연결 O/2번과 연결 O

2번 컴퓨터는 0번과 연결 X/1번과 연결 O/2번과 연결 O

-> 이중 리스트의 인덱스( i )는 연결 시작 노드이고

그 안의 리스트의 요소들( j )의 값( 0,1 )은 해당 노드와의 연결 유무

 

이를 첫 번째 for문과 두 번째 for문으로 에서 연결 시작 노드(start) 연결 끝 노드(end)로 작성하였고

해당 인덱스의 요소가 값이 1로 두 개의 노드가 연결되었을 때는 그래프에 추가합니다.

딕셔너리를 사용하여 키 값은 연결 시작 노드 값은 연결 끝 노드들 리스트 형식으로 그래프를 생성합니다.

예제 2 그래프 생성 결과 : {0: [1], 1: [0, 2], 2: [1]}

 

 

<BFS 반복>

입력을 딕셔너리 형태로 변환하여 그래프를 생성한 뒤

현재까지 방문한 노드와 그렇지 않은 노드를 저장하는 리스트를 만들어

while문을 사용하여 너비 우선 탐색으로 모든 노드를 방문할 때까지 반복합니다.

여기서 한 번의 탐색이 끝난 경우에도 아직 방문하지 않은 노드가 있다면  

현재 탐색한 노드와 연결되지 않은  다른 그룹의 노드들이 있는 것이기 때문에

네트워크 개수를 하나 더해줍니다.

 

 

BFS 너비 우선 탐색의 코드는 평범한 코드와 같습니다.

 

 

전체 파이썬 코드입니다.

<Python 코드>

 

def solution(n, computers):
    answer = 0
    graph = {}
    for start in range(n):
        graph[start] = []
        for end,edge in enumerate(computers[start]):
            if edge == 1 and start!=end :
                graph[start].append(end)
    visited=[]
    not_visited =list(graph.keys())
    while not_visited :
        visited += dfs(graph , not_visited [0])
        not_visited = list(set(graph.keys()) - set(visited))
        answer+=1
    return answer

from collections import deque
def bfs (graph , root):
    visited = []
    queue = deque([root])
    while queue :
        now = queue.popleft()
        if now not in visited:
            visited.append(now)
            queue+= list(set(graph[now])- set(visited))
    return visited

 

 

 

 

 

 

 

 

 

 

오늘의 교훈:

반복문 조건문을 쓸 때 단순한 값을 넣고 출력해서 내 의도대로 작동하는지 확인하자

처음에 while문을 while visited!=list( graph.keys()): 으로 썼는데

히든 테스트 케이스에서 계속 틀려서 오류를 못잡고 며칠 동안 방치해 두었다.

해결해보려고 한참 붙잡고있었는데 저렇게 쓰면 순서가 다르면 요소가 같아도 다르다고 판단해서 무한 반복한다.

어이없는 곳에서 한참 헤매서 짱났다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 출처 :

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

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