[lvl3]네트워크

출처: Programmers > 코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > 네트워크

문제 설명:

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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	computers	return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

입출력 예 설명

예제 #1

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

예제 #2

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

코드:

시도1:

  
from collections import deque
def solution(n, computers):
	# computers 정보로부터 그래프 딕셔너리 생성
    graph = {}
    for i in range(n):
        temp = set()
        for j in range(n):
            if computers[i][j] == 1 and i != j:
                temp.add(j)
        graph[i] = temp
    
    answer = []

	# 각 컴퓨터별로 bfs를 활용해 연결된 네트워크 리스트 확인
    for i in range(n):
        visited = []
        stack = deque([i])
        while stack:
            current_node = stack.popleft()
            visited.append(current_node)
            for adjacent_node in graph[current_node]:
                if adjacent_node not in visited:
                    stack.append(adjacent_node)
        visited.sort()
        if visited not in answer:
            answer.append(visited)

	# 연결된 네트워크 리스트에서 개수 리턴
    return len(answer)

시도 1 설명:

각 노드를 방문할 때마다 방문 목록(visited)을 생성
방문 목록은 각 노드에서 시작하는 전체 네트워크를 나타냄
방문 목록을 정렬하고, 이미 발견된 네트워크 목록에 없는 경우에만 answer에 추가

이 접근법의 문제는 이미 방문한 노드를 다시 방문할 수 있다는 것으로, 이는 불필요한 작업을 추가로 발생시킨다

시도 2(정답):

  
def solution(n, computers):
    answer = 0
    queue = []
    visited = []

    for a in range(n):
        if a not in visited:
            queue.append(a)
            answer += 1

            while queue:
                now = queue.pop(0)    
                for i in range(n):
                    if computers[now][i] == 1 and i not in visited:
                        visited.append(i)
                        queue.append(i)
    return answer

visited 리스트를 유지하여 이미 방문한 노드를 추적
이 리스트는 함수의 전체 실행 동안 유지되므로, 한 번 방문한 노드는 다시 방문하지 않는다
새로운 네트워크를 찾을 때마다 answer를 증가시킨다
불필요한 중복 작업을 피하므로 시도 1보다 효율적

우수답변자 코드:

answer 변수를 0으로 초기화
visited 리스트를 생성하고, 모든 원소를 0으로 초기화
내부 함수 dfs를 정의하여 DFS(Depth-First Search)를 구현
dfs 함수를 이용하여 네트워크를 찾음
while 반복문을 사용하여 모든 컴퓨터에 대해 네트워크를 찾음
새로운 네트워크를 찾을 때마다 answer를 1 증가
최종적으로 answer를 반환하여 네트워크의 개수를 구함

  
def solution(n, computers):
    answer = 0
    visited = [0 for i in range(n)]
    def dfs(computers, visited, start):
        stack = [start]
        while stack:
            j = stack.pop()
            if visited[j] == 0:
                visited[j] = 1
            # for i in range(len(computers)-1, -1, -1):
            for i in range(0, len(computers)):
                if computers[j][i] ==1 and visited[i] == 0:
                    stack.append(i)
    i=0
    while 0 in visited:
        if visited[i] ==0:
            dfs(computers, visited, i)
            answer +=1
        i+=1
    return answer

우수답변자2 코드:

temp 리스트를 생성하여 각 컴퓨터를 하나의 그룹으로 초기화
computers 배열을 탐색하며 연결된 컴퓨터들을 하나의 그룹으로 묶음
연결된 컴퓨터들의 그룹을 temp 리스트로 업데이트
중복을 제거하기 위해 set(temp) 사용
남은 그룹의 개수를 반환하여 네트워크의 개수를 구함

  
def solution(n, computers):
    temp = []
    for i in range(n):
        temp.append(i)
    for i in range(n):
        for j in range(n):
            if computers[i][j]:
                for k in range(n):
                    if temp[k] == temp[i]:
                        temp[k] = temp[j]
    return len(set(temp))

피드백:

첫 번째 코드의 비효율성과 중복 탐색 때문에 코드를 다시 짜야했다
두 번째 코드로 효율적이고 정확하게 문제를 해결할 수 있었다
테스트 결과는 다 pass해서 문제를 찾기 어려웠지만, 첫 번째 코드의 문제는 연결된 네트워크의 수를 과대 계산할 수 있으므로, 오답을 냈었다