[자료구조 및 알고리즘] DFS로 connected component 구하기(union find)

 

DFS를 활용해 connected component의 갯수를 구하는 것이 필요할 때가 있다. 이럴 땐 탐색을 하면서 각 unit별로 구분을 해서 갯수를 카운트 해주면 된다. 정확히는 이를 union find 알고리즘이라고 한다.

예제를 통해 이해해보자. 아래 문제는 프로그래머스에 수록된 문제이다.

programmers.co.kr/learn/courses/30/lessons/43162 

코딩테스트 연습 - 네트워크

def dfs(start, n, visited, computers):
    for i in range(n):
        if (i!=start) and (visited[i]==0) and (computers[start][i]==1):
            visited[i]=1
            dfs(i, n, visited, computers)
    
def solution(n, computers):
    answer = 0
    # 방문하면 1로 flag up
    visited = [0 for _ in range(n)]
    for i in range(n):
        if visited[i]==1:
            continue
        answer+=1
        dfs(i, n, visited, computers)
    return answer

 

위의 solution 함수에서 for문을 사용해 방문하고 answer+=1해주는 부분이 바로 connected component를 카운트하는 핵심이다. i에 방문을 하면 dfs(i)를 호출하게 되고 이 때 i와 연결된 여러 점들을 방문하고 방문처리한다. 그래서 dfs함수를 탈출하고나선 이미 i와 연결된 점들은 다 방문을 한 상태가 되어버린다. 따라서 solution 함수의 for문을 돌면서 visited가 False인 경우에만 방문을 다시 시도하게 되고 바로 이 때 answer를 +1 해주면 된다.