[백준] 4195번 : 친구 네트워크

유형 : 해시, 집합, 그래프

 

[예시]

2
3
Fred Barney
Barney Betty
Betty Wilma
3
Fred Barney
Betty Wilma
Barney Betty

[출력]

2
3
4
2
2
4

 

핵심 아이디어
1. 해시를 활용한 Union-Find 알고리즘을 이용
2. 딕셔너리 자료형을 해시처럼 사용 가능(파이썬)

 

1. 합집합 찾기(Union-Find) 알고리즘

- 원소들의 연결 여부를 확인하는 알고리즘

- 부모 테이블을 이용해서 현재 어떤 집합에 포함되어 있는지 확인

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)
    
    parent[y] = x
    
 parent = []   
 for i in range(0,5):
    parent.append(i)
 
 union(1,4)
 union(2,4)
 
 for i in range(1, len(parent):
    print(find(i), end=' ')

 

2. 풀이 - 예제 설명

1) 첫 번째 케이스

① Fred Barney

② Barney Betty

③ Betty Wilma

 

2) 두 번째 케이스

① Fred Barney
② Betty Wilma
③ Barney Betty

 

3. 소스코드

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
            
        if y not in parent:
            parent[y] = y
            number[y] = 1
        
        union(x,y)
    
    print(number[find(x)])

---

다시 해보자..

 

 

문제 출처 : https://www.acmicpc.net/problem/4195

4195번: 친구 네트워크

풀이 출처 : 패스트캠퍼스 - 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online