baekjoon 4195: 친구 네트워크

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

4195번: 친구 네트워크

친구관계의 소속?을 찾는 문제인데 문제를 처음에 읽고 union-find 개념이 생각이 났다.

---

생구현으로 union-find를 해결해 보려 했지만 시간초과..

t = int(input())
for tc in range(t):
    group = [0]*100000
    arr = []
    n = int(input())
    for nc in range(1,n+1):
        x,y = input().split()
        if x not in arr:
            arr.append(x)
        if y not in arr:
            arr.append(y)

        if group[arr.index(x)] ==0:
            group[arr.index(x)] =nc
        else:
            a=group[arr.index(x)]
            for i in range(len(group)):
                if group[i] != 0 and group[i] ==a:
                    group[i] = nc


        if group[arr.index(y)] ==0:
            group[arr.index(y)] = nc
        else:
            a=group[arr.index(y)]
            for i in range(len(group)):
                if group[i] !=0 and group[i] == a :
                    group[i] = nc

        cnt = 0
        for i in range(len(group)):
            if group[i] == nc:
                cnt +=1
        print(cnt)

---

시간에 대한 생각을 해보면 소속을 확인하기 위해 for문으로 group이란 list를 도는게 문제였다.

 

재귀적인 요소를 이용한다면 전체 list를 돌지않고 확인 가능할듯

(추가로, 친구들의 이름이 문자열이기 때문에 index개념을 사용하여 친구들의 소속을 관리 하기 어려우므로 딕셔너리 요소를 이용하였다.)

def find(a):
    if a ==group[a]:
        return a
    else:
        a_boss = find(group[a])
        group[a] = a_boss
        return group[a]

def union(x,y):
    x_boss = find(x)
    y_boss = find(y)

    if x_boss != y_boss:
        group[y_boss] = x_boss
        number[x_boss] += number[y_boss]

t = int(input())
for tc in range(t):
    group = dict()
    number = dict()

    n = int(input())
    for _ in range(n):
        x,y = input().split()

        if x not in group:
            group[x] = x
            number[x] = 1
        if y not in group:
            group[y] = y
            number[y] = 1
        union(x,y)
        print(number[find(x)])