[백준] 4195번 친구 네트워크 파이썬 해설 (디스조인트-셋)

출처 : https://www.acmicpc.net/problem/4195

4195번: 친구 네트워크

여러 가지 알고리즘으로 분류되어있는 문제이다.

디스조인트-셋(Disjoint-set) 알고리즘을 공부하기 위해 해당 알고리즘을 사용하였다.

 

풀이

---

디스조인트-셋 알고리즘에 대한 기본 지식은 위키백과를 참고하는 것을 추천한다. 읽어본 자료 중 설명을 가장 자세히 정리해둔 것 같다.

입력받는 이름을 노드, 이름의 친구 관계를 간선이라고 볼 수 있다.

문자열을 처리하기가 까다로워서 그런지 정답률은 낮은 문제였지만, 알고 보면 가장 기본적인 디스조인트-셋 알고리즘을 적용하면 쉽게 풀 수 있는 문제이다. (파이썬은 문자열 처리가 정말 편한 것 같다.)

먼저 디스조인트-셋 알고리즘에 사용할 세 가지 함수를 정의한다.

#부모 노드의 값을 얻는 함수
def getParent(parents, x):
    if parents[x] == x: return x
    #압축 과정 포함
    p = getParent(parents, parents[x])
    parents[x] = p
    return p

#두 부모 노드를 합치는 함수
def unionParent(parents,x1, x2, cnt):
    a = getParent(parents,x1)
    b = getParent(parents,x2)
    if a != b :
        parents[b] = a
        cnt[a] += cnt[b]

#루트 찾기
def findParent(x, parents):
    if parents[x] == x: return x
    return findParent(parents[x], parents)

위 세 가지 함수만 있다면 쉽게 문제를 풀 수 있다.

getParent함수는 딕셔너리 parents를 참조하여 부모 노드를 알 수 있는 함수이다.
입력받는 노드가 부모 노드로 되어있는 경우 그대로 반환하지만 그렇지 않을 경우 재귀 호출로 부모 노드를 계속 찾게 된다. 또한, 압축과정을 포함하여 이후에 접근 시 불필요한 재귀 호출을 막아준다.

unionParent함수는 두 노드를 합치는 역할을 하는 함수이다.
두 노드가 속한 집합의 부모 노드를 찾아 비교하게 된다. 부모 노드가 갖지 않다면 a를 기준으로 두 집합을 합쳐준다. 문제에서 친구(집합)의 수를 요구하므로, 원소의 개수를 저장하는 리스트 cnt도 업데이트해준다.

findParent함수는 입력받은 노드의 루트 노드를 찾아준다. 부모 노드를 찾는 것과 비슷하지만, 정답 코드의 가시성을 높이기 위해 필요한 부분만 따로 정의하였다. (압축과정 제거)

 

-정답 코드

import sys
input=sys.stdin.readline

#부모 노드의 값을 얻는 함수
def getParent(parents, x):
    if parents[x] == x: return x
    #압축 과정 포함
    p = getParent(parents, parents[x])
    parents[x] = p
    return p

#두 부모 노드를 합치는 함수
def unionParent(parents,x1, x2, cnt):
    a = getParent(parents,x1)
    b = getParent(parents,x2)
    if a != b :
        parents[b] = a
        cnt[a] += cnt[b]

#루트 찾기
def findParent(x, parents):
    if parents[x] == x: return x
    return findParent(parents[x], parents)

if __name__ == "__main__":
    for _ in range(int(input())):
        parents = {}
        cnt = {}
        for test in range(int(input())):
            friend1, friend2 = input().split()

            if friend1 not in parents:
                parents[friend1] = friend1
                cnt[friend1] = 1

            if friend2 not in parents:
                parents[friend2] = friend2
                cnt[friend2] = 1

            unionParent(parents, friend1, friend2, cnt)
            print(cnt[findParent(friend1, parents)])

1. 두 사람의 이름을 입력받은 후 아직 딕셔너리 parents에 없는 이름이라면 추가해준다.
2. 두 이름을(이름이 속한 집합을) 합쳐주어 친구 관계를 만든다.
3. 현재까지 해당 친구관계를 포함하여 같은 집합에 있는 원소의 개수를 출력한다.

 

결과

---

오늘도 한 번의 시도만에 문제를 맞혔다.

횟수는 중요하진 않지만 그냥 하루 시작을 기분 좋게 할 수 있는 것 같다.