[프로그래머스] 네트워크(LV3 - Python) - Union-Find(유니온 파인드) 알고리즘

프로그래머쓱

해당 글에서는 네트워크 문제를 Python을 이용해 풀이하고자 한다.

해당 문제는 Union-Find를 사용하는 대표적인 문제로, 해당 알고리즘을 까먹어 다시 상기하고자 다시 풀이했다!

프로그래머스

 

🔷 문제 설명

 

🔷 문제 풀이

해당 문제를 풀기 위해선 Union-Find의 개념에 대해 알아야 한다.

이는 서로소 집합을 찾는 알고리즘으로, 서로소 집합은 공통 원소가 없는 두 집합을 의미한다.

 

네트워크를 찾는 과정이 서로소 집합을 찾는 과정에 해당하며, 따라서 Union-Find를 이용하면 된다.

 

1️⃣ Python 풀이

def find(parent, x): # 부모 찾기
    if parent[x] != x:
        parent[x] = find(parent, parent[x]) # 루트 노드가 아닌 경우, 재귀호출을 통해 루트 노드를 찾음
    return parent[x]

def union(parent, x, y): # 합치기
    x = find(parent, x)
    y = find(parent, y)
    
    if x < y:
        parent[y] = x
    else:
        parent[x] = y
    
def solution(n, computers):
    answer = 0
    
    parent = [i for i in range(n)]
    for i in range(n):
        for j in range(n):
            if i!=j and computers[i][j]:
                union(parent, i, j)
    
    for i in range(n):
        find(parent, i)
    answer = len(set(parent))
    
    return answer

 

여기서 주의해야 할 점은 다음 코드라고 생각한다.

처음에 아래 코드 없이 제출했다가 틀린 결과를 확인할 수 있었는데, 다음의 반례를 통해 아래 코드가 문제를 푸는데 필요한 이유를 찾아볼 수 있었다.

for i in range(n):
    find(parent, i)
answer = len(set(parent))

 

다음과 같은 입력이 주어진 경우, 위 코드가 없으면 parent 결과는 당장의 부모가 아니게 된다.

• 0, 1, 2번 노드가 있고, [1, 2], [0, 1]번 노드가 연결되어 있는 경우
  • [1, 2]번 연결 처리
    parent = [0, 1, 1]
  • [0, 1]번 연결 처리
    parent = [0, 0, 1]

즉, 원래 결과는 하나의 네트워크 이므로 [0, 0, 0]이어야 하지만, [0, 0, 1]이 결과로 출력돼 틀리게 된다.

따라서 위 코드와 같이 부모 배열을 한 번 갱신해주는 코드가 필요한 것이다.

 

아직도 헷갈린다면, 아래의 질문 글을 참고하자!

프로그래머스

---

문제가 있어 질문 게시판을 보던 도중 과거의 나를 발견했다는...