[프로그래머스][Python] 네트워크

문제를 정리해보자.

 

A와 B가 직접적으로 연결되어 있고 B와 C가 직접적으로 연결되어 있다면,

A와 C는 간접적으로 연결된 것이다.

따라서 A, B, C 모두 연결되어 있다. 이를 모두 같은 네트워크상에 있다고 한다.

 

몇 개의 네트워크가 있는지 구하는 문제이다.

 

제한사항과 입출력 예를 보자.

 

 

 

 

[[1, 1, 0], [1, 1, 0], [0, 0, 1]]은 양방향이다. 표로 나타내면 아래와 같다.

1이면 길이 있고, 0이면 길이 없다.

 

 

 

 

풀이를 생각해보자.

 

예를 들어보자. 노드는 12개이다. 네트워크는 3개이다.

 

 

 

시작노드 0번을 연결된 노드를 확인한다.

0번 -> 1번 -> 2번 -> 5번 -> 7번 -> 6번 -> 3번 -> 4번 이렇게 직접적으로 연결된 부분을 확인한다. (DFS)

 

다음 시작노드는 1번이다. 하지만 1번 노드는 이미 0번 노드와 연결되어 있음을 확인했다.

따라서 2~7번 노드도 시작노드가 되지 않는다.

 

다음 시작노드는 8번이다. 8번 -> 9번 -> 10번

 

다음 시작노드는 11번이다. 연결된 노드는 없지만, 하나의 네트워크를 가지고 있다고 생각한다.

 

 

구현해보자.

 

DFS로 구현했다. 방문했던 노드를 재방문하지 않는 것이 핵심이다.

 

DFS로 시작노드와 직, 간접으로 연결되어 있는 모든 노드를 확인한다.

이는 하나의 네트워크에 연결된 노드들을 찾는 것이다.

 

 

def dfs(start_n, graph, check, tmp):
    check[start_n] = 1

    for i in graph[start_n]:
        if check[i] == 0:
            dfs(i, graph, check, tmp)


def solution(n, computers):

    # 입력
    graph = [[] for _ in range(n)]

    for i in range(len(computers)):
        for j in range(n):
            if computers[i][j] == 1:
                graph[i].append(j)
                graph[j].append(i)

    # 구현
    check = [0] * n
    tmp = 0
    answer = 0

    for start_n in range(n):
        if check[start_n] == 0:  # 방문하지 않은 노드
            if not graph[start_n]:  # 연결 노드가 없는 노드
                check[start_n] = 1
                answer += 1

            else:  # 연결 노드가 있는 노드
                dfs(start_n, graph, check, tmp)
                answer += 1

    return answer


print(solution(3, [[1, 1, 0], [1, 1, 0], [0, 0, 1]]), 2)

 

 

시간 복잡도는 O(N)이다.