백준 4195: 친구 네트워크 (Python)

 

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

4195번: 친구 네트워크

 

입력받는 요소가 사람이름이기 때문에 숫자로 관리하기 위해 딕셔너리(people)를 선언하고

1. a, b 입력받아서

2. 딕셔너리에 존재하지 않으면 추가, parent 추가

3. union

그 후 연결되어 있는 요소들의 개수를 출력하기 위해

원래 count 함수를 썼는데 제대로 못 잡아내길래 for문을 썼다

 

ㅎㅎ시간초과

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

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

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b

t = int(input())

for i in range(t):
    f = int(input())
    people = dict()
    parent = []
    count = 0

    for j in range(f):
        a, b = input().split()

        if a not in people:
            people[a] = count
            parent.append(count)
            count += 1

        if b not in people:
            people[b] = count
            parent.append(count)
            count += 1

        a = people[a]
        b = people[b]
        union_parent(parent, a, b)

        check = find_parent(parent, a)
        res = 0
        for k in range(len(parent)):
            if check == find_parent(parent, parent[k]):
                res += 1
        print(res)

 

우선 people 제거 -> parent를 딕셔너리로 만들어서 관리

기존 union 함수는 숫자로 관리하기 때문에 함수 수정

result 딕셔너리 추가 -> 결과값을 저장

 

parent에 새로운 데이터가 추가될 때 result + 1

union 함수를 통해 네트워크를 형성할 때 두 사람의 연결 관계를 모두 합친 값을 부모 result에 저장한다.

(모든 요소의 result 값을 업데이트하기 힘듦)

결과값을 출력할 때 부모를 찾아서 부모의 result 값을 출력해주면 된다.

 

결과는,,, 맞았습니다!!

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

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

def union_parent(a, b):
    a = find_parent(a)
    b = find_parent(b)

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

t = int(input())

for i in range(t):
    f = int(input())
    parent = dict()
    result = dict()

    for j in range(f):
        a, b = input().split()

        if a not in parent:
            parent[a] = a
            result[a] = 1

        if b not in parent:
            parent[b] = b
            result[b] = 1

        union_parent(a, b)
        print(result[find_parent(a)])