SWEA-5521-상원이의 생일파티
상원이(1번)의 친구가 인접리스트 형태로 주어지고 상원이의 친구의 친구(트리로 치면 depth가 2인 노드까지)가 몇명인지 구하는 문제
- 딕셔너리 형태로 친구관계를 정리한다
- dfs를 통해 depth 2인 노드까지 구할 것임
- 1번 key(상원이)에 속한 value(친구들)를 꺼내고 다시 해당 value를 key값으로 사용하여 dfs로 던져준다.
input_case_num = int(input())
def dfs(list, depth):
if depth == 2 or not list:
return
for i in list:
invite_friend.add(i)
dfs(direct_friend.get(i), depth+1)
for T in range(1, input_case_num+1):
TS, BF = list(map(int, input().split())) # 전체 학생 수, 친한 친구 수
R = {}
direct_friend = {i: [] for i in range(1, TS+1)}
for _ in range(BF):
s1, s2 = list(map(int, input().split()))
direct_friend.get(s1).append(s2)
direct_friend.get(s2).append(s1)
invite_friend = set()
dfs(direct_friend.get(1), 0) # 친구1(상원이)리스트를 던져주고 친구의 친구(depth=2)까지 초대할 친구에 넣는다
invite_friend.add(1)
print('#{} {}'.format(T, len(invite_friend)-1))
Author And Source
이 문제에 관하여(SWEA-5521-상원이의 생일파티), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@uykgnod/SWEA5521상원이의-생일파티저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)