오늘의 알고리즘(4월 14일, feat.Union Find)

1. 백준, 친구 네트워크, 4195번

 

www.acmicpc.net/problem/4195

4195번: 친구 네트워크

---

2. 생각해보자 

 

- 입력값은 다음과 같다.

• 2는 테스트 케이스의 수(N) 
• 3은 친구 관계의 수(F) / F는 100,000을 넘지 않음
• 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 
• 친구 관계는 두 사용자의 아이디로 이루어져 있다 / 알파벳 대문자 또는 소문자로 길이 20 이하의 문자열
• 친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇명이 있는지 구하는 프로그램을 작성해라 

 

 

무엇을 어떻게 계산하라는 거지?

• 예제 입력에서 Fred Barney는 한 사람의 이름이 아니라 Fred와 Barney, 두명의 이름이다. 
• Fred와 Baney의 인간관계(조합)는 2개
• Barney와 Betty는 2개 + Barney와 Fred의 관계 1개 = 총 3개
• 이런식으로 문제를 풀면 되는 것이었다. 

 

 

나는 어떻게 풀 것인가?

• F를 N번만큼 입력받아야 한다.
• F번 만큼 for 반복문을 돌린다.
• for 반복문이 한번 회전할 때마다 입력을 받고 출력을 한다. 이는 총 F번의 입출력을 의미한다. 
• N번의 반복문이 한바퀴 돌 때마다, 또 다른 테스트 케이스를 위하여 리스트는 초기화 된다. 

n = int(input())

for n_count in range(n):
    f = int(input())
    network = []
    for f_count in range(f):
        network.append(input().split(' '))
        if len(network) < 1:
            print(2)
            
        else: ?????? 

 

- 뭔가... 깊이 탐색? 같은 느낌으로 가야할 것 같은데 잘 모르겠다. 

 

---

3. 해설 및 코드분석

• 해당 문제는 해시를 활용한 Union Find(= 합집합) 알고리즘을 사용하여 풀 수 있다.
  - Union Find 알고리즘은 원소들의 연결여부를 확인하는 알고리즘이다. 
• Python의 dictionary 자료형을 해시처럼 사용할 수 있다.  

 

 

a) Union Find 알고리즘 이란?

devraphy.tistory.com/82

Advanced Algorithm - MST(Union-Find Algorithm)(2)

 

 

b) 코드

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

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

    if x != y:
        parent[y] = x
        number[x] += number[y]

test_case = int(input())

for _ in range(test_case):
    parent = dict()
    number = dict()

    f = int(input())

    for _ in range(f):
        x, y = input().split(' ')

        if x not in parent: # 부모노드를 없는 경우
            parent[x] = x 
            number[x] = 1 
            #부모노드가 없으면 원소 자체가 부모노드이니까 네트워크 값을 1로 설정

        if y not in parent: # 부모노드를 없는 경우
            parent[y] = y
            number[y] = 1 
            #부모노드가 없으면 원소 자체가 부모노드이니까 네트워크 값을 1로 설정
        
        union(x, y)
        
        print(number[find(x)])