문제 설명

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

해결 전략

문제 상황을 잘 뜯어보면 서로소 집합의 개수를 구하는 문제임을 알 수 있었다.
그래서 유니온 파인드 알고리즘을 이용해서 풀려고 시도 했다.
하지만 이 문제에서는 예외 상황이 생길 수 있는데 배열을 다 돌면서 서로소 집합을 만들었을 때
연결되는 순서에 따라서 union 했을 때 부모가 제대로 안잡힐 수 있다는 점이었다.
나는 이 부분에 대한 입력을 못 찾아내서 질문하기에 있는 테스트 케이스를 찾았다.
이 부분에 대한 해결 방안은 마지막으로 parent 배열을 i번째의 부모를 찾아서 넣어주면 해결 할 수 있다.

보완

테스트 케이스가 복잡할 때 예제를 만드는게 어려운 거 같다.
어떻게 예외가 날 만한 예제를 만들어서 넣을 수 있을까는 문제를 많이 풀어 보면서 계속 예제를 만드는 연습을 해 보아야 할 거 같다.

또한 이 문제를 풀면서 union find알고리즘을 안보고 구현하려 했으나 union부분을 구현하는데 실패해서 결국 구글링한 union find 알고리즘을 이용해서 문제를 풀었다
union find 알고리즘은 다시 블로그에 정리해서 올려야겠다.

코드

def solution(n, computers):
    
    answer = 0
    
    parent = [i for i in range(n)]
    
    def find(target):
        if target == parent[target]:
            return target
    
        parent[target] = find(parent[target])
        return parent[target]
    
    def union(a, b):
        a = find(a)
        b = find(b)
    
        if a < b:
            parent[b] = a
        else:
            parent[a] = b
    
    #배열을 싹다 돌면서 연결되어 있는 경우 부모를 찾아낸다.
    for i in range(n):
        for j in range(n):
            if computers[i][j] == 0:
                continue
            union(i, j)
    
    #예외처리
    for i in range(n):
        parent[i] = find(i)
    
    answer = len(set(parent))
    
    return answer