5174. [파이썬 S/W 문제해결 기본] 8일차 - subtree

[문제]
https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AWTay1Z64cQDFAVT&categoryId=AWTay1Z64cQDFAVT&categoryType=CODE&problemTitle=&orderBy=PASS_RATE&selectCodeLang=ALL&select-1=2&pageSize=10&pageIndex=1&&&&&&&&&&

[해설]
이진트리 문제이다.

부모와 자식 관계를 표현한 2차원 배열에 대해 dfs로 해결할 수 있다.

T = int(input())
def get_count(tree, n ,visited):
    global cnt #전역변수로 cnt 사용
    visited[n] = True #방문 노드 True로 변경

    if not tree[n]: #자식이 없으면 탈출
        return 0
    else:
        for i in tree[n]: #자식을 순회하면서
            if not visited[i]: #방문하지 않은 노드라면
                cnt += 1 #개수 +1 
                get_count(tree, i, visited) #들어가면서 순회

for tc in range(T):
    E, N = map(int, input().split()) #엣지 개수와 목표 노드
    tree = [[] for _ in range(E+2)] # 1번부터 노드로 사용하기위해 E+2만큼 입력받음
#원래 노드 개수는 E+1개
    visited = [False] * (E+2) #방문배열 초기화
    nodes = list(map(int, input().split())) #노드 입력받기
    cnt = 0

    for i in range(0, len(nodes), 2):
        parents = tree[nodes[i]] #부모 입력
        parents.append(nodes[i+1]) #자식추가
    get_count(tree, N, visited)
    print(f"#{tc+1}", cnt+1)# 자기자신 +1


+1