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

---

문제 링크

---

깊이 우선 탐색(DFS/BFS) 유형이었지만, 나는 Union-Find 알고리즘이 가장 먼저 떠올랐다.

import sys
input = sys.stdin.readline

def solution(n, computers):
    def find_parent(parent, x):
        while parent[x] != x:
            x = parent[x]
            
        return parent[x]

    def union_parent(parent, a, b):
        a = find_parent(parent, a)
        b = find_parent(parent, b)
        if a < b:
            parent[b] = a
        else:
            parent[a] = b
    
    parent = [0] * n
    
    for i in range(n):
        parent[i] = i
    
    for i in range(n - 1):
        for j in range(i + 1, n):
            if computers[i][j] == 1:
                union_parent(parent, i, j)
        
    answer = n
    for i in range(n):
        if parent[i] != i:
            answer -= 1
            
    return answer

처음에 나는 find_parent 메서드를 재귀로 작성했다.

    def find_parent(parent, x):
        if parent[x] != x:
            parent[x] = find_parent(parent, x)
            
        return parent[x]

하지만 python은 재귀제한이 걸려있어서 재귀 허용치가 넘어가면 런타임에러를 일으킨다.

RecursionError: maximum recursion depth exceeded in comparison

그래서

import sys
sys.setrecursionlimit(10**9)

이렇게 추가로 허용할 수 있도록 했지만

signal: segmentation fault (core dumped)

이런 에러가 출력됐다. 스택오버플로우가 된 듯하다.
그래서 recursive 함수가 아닌 iterative 함수로 변경했다.

    def find_parent(parent, x):
        while parent[x] != x:
            x = parent[x]
            
        return parent[x]

또한 나는 parent의 배열값이 다르면 다른 네트워크 상에 있다고 판단해서
리턴값을 len(set(parent))로 설정했는데 테스트가 4개만 통과하면서 실패했다.,,
질문하기 탭에 가서 관련 질문들을 보면서 다음 코드로 수정했다.

    answer = n
    for i in range(n):
        if parent[i] != i:
            answer -= 1

이렇게 고치니까 바로 통과했다. 머가 문젠진 set로 해서 개수를 리턴하는 게 왜 잘못된 건진 모르겠다 ㅠㅡㅠ ..

DFS/BFS 알고리즘으로도 풀어봐야겠다