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

문제 설명

간단히 말하여 net의 수를 구하는 문제이다.

이와 유사한 문제는 삼성 코딩테스트, 백준의 컴퓨터 네트워크 수 구하기, 크루스칼 알고리즘 등에서 보이듯, 기본문제이다.

주어진 그래프의 자료형은 인접행렬(2차원 행렬)으로 주어졌고 무방향 그래프이다.

문제 접근

1. Union Find

   한 그래프와 다른 한 그래프의 노드를 비교하여 서로 다른 그래프에 속해있다면 합쳐준다. 같은 그래프에 속해있는지 판단하는 방법은 서로의 루트노드가 같은지 비교하면 된다.

2. BFS,DFS

   깊이우선 탐색. 모든 노드에 대해 방문했는지 체크해주는 visited 리스트 or 비트를 구현하고 한 노드에 대해 탐색 후 탐색이 안된 노드를 찾아 탐색해주면 된다. 탐색이 안된 노드를 찾아 탐색하는 횟수가 곧 그래프의 수. 왜냐하면 DFS또는 BFS 탐색 시 서로 연결된 노드를 모두 탐색하므로 탐색이 안된 노드는 연결된 노드가 아니다 -> 같은 그래프에 속해있는 노드가 아니라고 말할 수 있기 때문.

Union Find 알고리즘을 복습하기 위해 이 문제를 선택했으므로 Union Find로 접근해보았다.

1.모든 엣지에 대해 탐색

• 무방향 그래프이므로 (u,v)에 대해 탐색했다면 (v,u)는 탐색하지 않아도 된다. (여기서 u,v는 vertex를 의미)

2.서로 연결되어 있는지 확인

• 인접행렬의 값이 연결 여부를 판단하므로 이 값이 1인지 0인지 확인하면 된다.

3.연결되어 있다면 u에 속한 그래프에 v를 넣어준다.

• 이 작업은 유니온 파인드에서 v의 루트노드를 u의 루트노드 설정해주는 방식으로 그래프를 이어준다.

4.모든 연결 작업이 끝났다면 모든 노드를 탐색하여 루트노드의 수를 구한다.(비효율 느끼는 부분)

• 루트노드의 수가 곧 그래프의 수이므로 위와 같은 작업 실행(set 이용)
• 이 작업은 비효율을 느끼는 점으로, 루트노드를 탐색할 때 시간 자원을 많이 소모한다. 순수~ Union Find알고리즘만을 사용했으므로 좀 오래 걸리겠다.
  이전에 이 문제를 해결하기 위해 v가 속한 그래프의 모든 노드에 대해 u의 루트노드로 연결해주는 방식으로 해결해보긴 했다. 어차피!! 연결관계가 중요한 것이 아닌, 어디 그래프에 속하느냐가 중요한 문제이므로. 정보를 잃지만 속도는 높히는 방법.

구현

def solution(n, computers):
    parents = [i for i in range(n)]

    def FindRoot(node):
        parentNode = parents[node]
        if parentNode != node:
            return FindRoot(parentNode)
        else:
            return parentNode

    def UnionSet(node1, node2):
        rootNode1 = FindRoot(node1)
        rootNode2 = FindRoot(node2)
        if rootNode1 == rootNode2:
            return
        else:
            parents[rootNode1] = rootNode2
            return

    def CountRoot(parents):
        roots = set()
        for i in range(n):
            roots.add(FindRoot(i))

        return len(set(roots))

    for node1 in range(n):
        for node2 in range(node1,n):
            if computers[node1][node2]:
                UnionSet(node1, node2)

    return CountRoot(parents)