네트워크

Last updated Nov 22, 2022 Edit Source

• Lv 3
• Dfs

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

def dfs(node, computers, visited):
    visited[node] = True 
    
    for i, neighbor in enumerate(computers[node]):
        # 인접노드 중 자기 자신이 아니고 아직 방문하지 않은 노드에 대해 
        if neighbor > 0 
        and i != node 
        and visited[i] == False:
            dfs(i, computers, visited)
    return visited
    

def solution(n, computers):
    answer = 1
    visited = [False] * n
    start_node = 0
    
    while True:
        visited = dfs(start_node, computers, visited)
        
        if False in visited:
            start_node = visited.index(False)
            answer += 1
        else:
            break
    
    return answer

이 문제는 깊이 우선 탐색, DFS 알고리즘을 이용해 푸는 문제다. 이번에는 연결된 노드가 인덱스가 아니라 연결됨(1)과 연결되지 않음(0)으로 주어져서, 따로 enumerate 함수로 인덱스를 가져와서 풀어야 했다. 우선 0번째 컴퓨터부터 시작해서 이와 직/간접적으로 연결되어 있는 모든 컴퓨터들 방문한다. 이후에도 아직 방문하지 않은 컴퓨터가 있으면 answer를 하나씩 증가시키고, 방문하지 않은 컴퓨터 중 번호가 가장 작은 것에서부터 시작해 다시 dfs를 호출한다. 마지막으로 모든 컴퓨터를 방문하면 반복을 종료하고 answer를 반환합니다.