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))