[BOJ / 백준 4195번][PYTHON] 친구 네트워크 (유니온 파인드)

유니온 파인드 3번째 예시 문제로 두 사람의 친구 네트워크에 몇 명이 있는 지 구하는 것이다.

입력으로는 친구 관계가 입력으로 들어오고 친구 관계가 생길 때마다 친구 네트워크가 몇 명이 있는 지 구하는 프로그램을 작성하는 것이다.

즉, 유니온 파인드의 개념으로 생각을 해본다면 친구 관계라는 것은 결국 하나의 집합이다. 친구 관계가 들어올 때마다 기존의 집합에 새롭게 합집합으로 추가되는 개념이다. 

 

이 문제의 난이도는 골드 2로 지난 문제가 보통 골드 4-5에 비하여 살짝 어려워졌다. 그렇다면 뭐가 다를까 하면 입력이 문자열이라는 것이다. 친구의 이름은 당연하게도 숫자가 아닌 문자열로 들어오게 된다. 그렇다면 이 문자열을 어떻게 관계 잡아 처리할 지가 관건이었다. 

그리하여 생각한 방법은 문자열이 들어올 때마다 기존의 것이 아닌 새로운 것이 들어온다면 count 변수 비슷한 개념으로 count 증가를 시키고 그 값을 배열의 인덱스 값으로 사용하는 것이다.

 

예를 들어 fred barney, barney betty, betty wilma가 들어온다면, 1번째의 fred는 0번 or 1번 인덱스 (처리하기 편한대로 설명하기 편하게 하기 위하여 여기서는 1번으로 하겠다.)

가 될 것이고 barney는 count 변수 2의 값을 갖게 될 것이다.

이 상황에서 2번째 줄에서 barney가 다시 들어오게 되는데 이 값은 3이 아닌 이미 들어온 값이기 때문에 2의 값을 건드리지 않고 betty가 새로 들어오기 때문에 3의 값을 갖게 된다. 이와 같이 입력을 처리하게 되며, 다음 같은 집합에 해당하는 union 연산을 하기 위해 이 할당 값을 배열의 index와 같은 의미로 처리를 한다. 그리하게 되면 1번 인덱스의 의미는 fred가 되며, 2번은 barney가 되고 해당 인덱스의 값은 집합의 번호가 되게 된다. 그 다음 과정은 크게 다르지 않다.

 

정리해보면, 이 문제는 입력으로 문자열이 들어오게 되는데 이거를 어떻게 index값과 동일하게 처리를 할 수 있는가, 그리고 유니온 파인드의 개념을 이해하고 똑같이 만들 수 있는가 이게 전부인 문제이다. 아래는 구현 코드이다.

import sys

n = int(sys.stdin.readline())

def find(x):
    if arr[x] != x:
        arr[x] = find(arr[x])
    return arr[x]
        
def union(x, y):
    a = find(x)
    b = find(y)
            
    if a != b:
        arr[b] = a
        size[a] += size[b] 

    return size[a]

for _ in range(n):
    arr = []
    size = []
    temp = int(sys.stdin.readline())
    name = {}
    count = 0

    for i in range(temp):
        s = sys.stdin.readline().split()
        
        if s[0] not in name:
            name[s[0]] = count
            arr.append(count)
            count += 1
            size.append(1)
    
        if s[1] not in name:
            name[s[1]] = count
            arr.append(count)
            count += 1
            size.append(1)
    
        result = union(name[s[0]], name[s[1]])
        print(result)

해당 구현에서 보면 기존에 설명하지 않은 size 배열이 존재한다. 여기서 말하는 size 배열은 중요한 것은 친구 관계의 수가 몇명인지 이기 때문에 계속하여 집합 전체의 크기를 더해주게 되는데 이 연산이 배열을 훑어가며 확인해야 하기 때문에 시간이 오래걸리게 되기 때문에 이것을 size배열을 통해서 빠르게 가져올 수 있도록 장치를 준 것이다.