4195 친구 네트워크 _python

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

4195번: 친구 네트워크

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 접근

Union-Find 문제

https://portable-paper.tistory.com/entry/Union-Find-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

Union & Find 알고리즘

Dictionary를 만들어서 이름을 번호로 바꿔 관리하면 편하다.

입력받은 친구 2명을 ddictionary와 parent목록에 추가시켜준다.

parent목록을 사용해서 union-find를 구현한다.

마지막으로 입력으로 들어온 친구가 친구네트워크에 몇명이 있는지 세면 끝이다.

 

첫 시도에서 시간초과가 났다...

친구네트워크에 몇명이 있는지 세기위해 매번 모든배열을 find로 탐색을 했고, 최대 10만번까지 반복하며 시복이 O(N^2)만큼 될것 같았다.

그래서 union하는 과정에서 약간 수정을 해줬다.

union의 매개변수의 두 값인 x,y의 find(x)와 find(y)를 비교해서 연결하는 다르다면 그냥 아무렇게 연결하도록 바꾸고,

if a!=b: parent[a] = b

여기에 친구네트워크의 친구 수도 같이 계산해서 더하도록 추가했다.

그리고 이 값만 그대로 출력하면 답이 나오도록 만들었다.

if a!=b: 
        parent[a] = b
        friendCount[b] += friendCount[a]

 

 

 

다른 블로그를 보니까 사전을 2개 만들어서 사용하던데... 이해하기도 더 어렵고, 시간도 더 걸릴것 같아서 딕셔너리1개와 배열2개로 구현했다.

메모리가 500kb정도 더 적고 시간이 40ms정도 더 빠르게 나왔다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

코드

import sys
input = sys.stdin.readline

"""
4195 친구 네트워크
Union-Find
dictionary에 이름과 몇번째인지 저장.
사전을 보고 해당 친구의 부모(?)가 같은지 비교??? 알고보니 잃어버린 친동생인가?
각 입력이 끝나고 부모가 같은.......시간초과
미리 개수를 저장하면서 사용.
"""

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
        return parent[x]
    return x

def union(x,y):
    
    a = find(x)
    b = find(y)
    if a!=b: 
        parent[a] = b
        friendCount[b] += friendCount[a]

T = int(input())
for _ in range(T):
    F = int(input())
    nameInfo = {}
    curNum = 0
    parent = []
    friendCount = []

    for i in range(F):
        x, y = input().split()

        if x not in nameInfo:   #dictionary에 없으면
            nameInfo[x] = curNum    #dictionary에 추가
            parent.append(curNum)   #부모목록에도 추가
            friendCount.append(1)   #친구 숫자 새는곳에도 추가.
            curNum += 1

        if y not in nameInfo:
            nameInfo[y] = curNum
            parent.append(curNum)
            friendCount.append(1)
            curNum += 1
            
        union(nameInfo[x], nameInfo[y])

        print(friendCount[find(nameInfo[x])])

60828KB  332ms