[Baekjoon Online Judge] 백준 4195번 친구 네트워크(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 4195번 친구 네트워크

(Python)

(글쓴날 : 2020.06.15)

 

---

* Baekjoon Online Judge, 백준 4195번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 4195번 친구 네트워크

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/4195

4195번: 친구 네트워크

---

2) 풀이 과정

* 시간 복잡도 : O(α(n), α : 아커만 함수)

 

소셜네트워크 상의 친구 관계가 생긴 순서대로 주어질 때, 주어지는 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 문제입니다.

 

저의 경우, 유니온 파인드를 적용하였고, Python을 사용했습니다.

처음에는 파이썬의 딕셔너리를 이용해 네트워크들을 만들어가며 해당 네트워크에 있는 친구들의 수를 모두 세가는 식으로 접근했으나 시간 초과가 발생했습니다.

그래서 한 네트워크에 속한 친구들 수를 저장해놓을 딕셔너리를 추가로 생성하여 문제를 해결했습니다.

주의해야 할 점은, 집합을 합치는 union() 함수에서 네트워크를 합칠 때마다 각 네트워크에 속한 친구들의 수 더하는데, 이미 같은 집합일 경우를 고려하지 않는다면 중복으로 친구들의 수가 더해지게 되어 출력 초과가 발생합니다. 따라서, 보통의 경우에 union() 함수 구현을 if와 else 즉, 작은 경우와 그렇지 않은 경우 두 가지 갈래로 분기하지만, 이번 문제처럼 카운트를 세어야 하는 경우에는 else를 사용하지 않고 정확히 작은 경우와 큰 경우를 명시하여 분기하거나, 두 노드의 find() 값이 같을 경우 바로 리턴하는 예외 처리를 해주셔야 합니다.

(아래 코드의 17 ~ 22번째 라인에 대한 설명입니다.)

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
 
def find(target):
    if table[target] == target:
        return target
 
    table[target] = find(table[target])
    return table[target]
 
 
def union(f1, f2):
    foundF1 = find(f1)
    foundF2 = find(f2)
 
    if foundF1 < foundF2:
        count[foundF1] += count[foundF2]
        table[foundF2] = foundF1
    elif foundF1 > foundF2:
        count[foundF2] += count[foundF1]
        table[foundF1] = foundF2
 
 
TC = int(input())
 
for _ in range(TC):
    F = int(input())
 
    table = dict()
    count = dict()
 
    for _ in range(F):
        ans = 0
        friendship = input().rstrip().split()
        
        for name in friendship:
            if not table.get(name, 0):
                table[name] = name
                count[name] = 1
        
        union(friendship[0], friendship[1])
 
        print(count[find(friendship[0])])

---