Python3/백준 알고리즘
2022.05.31 [백준] (python 파이썬) 친구 네트워크
ian's coding
2022. 5. 31. 22:10
728x90
반응형
https://www.acmicpc.net/problem/4195
4195번: 친구 네트워크
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진
www.acmicpc.net
풀이
이 문제는 두개의 딕셔너리를 이용하여 해결했다. 우선 x, y를 입력받고 x, y가 딕셔너리에 들어있지 않다면 자신의 이름을 value로 가지게 friends딕셔너리에 넣고, 친구의 수를 기록할 딕셔너리 number에 value를 1로 넣는다.
그리고 union함수에 x,y를 넣는다.
여기서 각각의 root node를 찾아주기 위해 find_parent함수에 x, y를 넣어준다.
만약 자신의 루트노드면 자신을 반환하고, 아니면 해당 노드의 value를 root node로 업데이트해준다.
이후, root_x와 root_y가 같지 않으면 서로 공유하고 있는 친구가 없기 때문에 root_y의 value 즉 root node를 root_x로 바꿔준다. 그리고 root_x의 친구의 수에 root_y의 친구 수를 더해준다.
그리고 x를 기준으로 친구 수와 root node를 업데이트했기때문에 출력을 할때 x의 root node를 구해 해당 값의 number값을 출력한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
# x에 대한 root node 찾는 함수
def find_parent(x):
if x==friends[x]:
return x
else:
# 각 하위 노드의 value를 모두 root node로 바꿔줌
# 값이 커지면 순회하는 시간이 줄어듦
root_x=find_parent(friends[x])
friends[x]=root_x
return friends[x]
def union(x,y):
# x, y의 root node를 찾음
root_x=find_parent(x)
root_y=find_parent(y)
# x, y의 root node가 같지 않으면
# y의 root node가 x의 root node의 자식이 되도록 함
# 그리고 root_x의 친구 수에 root_y의 친구 수를 더함
if root_x!=root_y:
friends[root_y]=root_x
number[root_x]+=number[root_y]
for i in range(int(input())):
friends = {}
number = {}
for j in range(int(input())):
x,y=input().split()
if x not in friends:
friends[x]=x
number[x]=1
if y not in friends:
friends[y]=y
number[y]=1
union(x,y)
# 위의 함수에서 x, y의 root node가 같지 않으면
# x의 root node가 y의 root node가 되도록 했기 때문에
# x의 root node의 값을 찾아서 갯수를 출력함
print(number[find_parent(x)])
|
cs |
728x90
반응형