Tree - subtree

1. Tree의 부모-자식 관계를 저장할 새로운 리스트를 선언하고(tree)

• E(간선 수)에 2를 더한만큼 공간을 생성해주는데,
  1) 노드의 수는 간선+1이기 때문에
  2) 계산의 수월함을 위해 (0행은 값이 비워지게 되고 1행부터 값이 들어간다.)

2. 2의 간격을 둔 for문을 통해 Tree 리스트에 서브트리를 저장한다.
3. 서브트리 순회. 재귀를 통해 서브트리를 끝까지 돌아준다.

def dfs(N):
    global cnt
    cnt+=1
    for i in tree[N]:
        dfs(i)

for tc in range(1,int(input())+1):
    E,N = map(int,input().split())
    arr = list(map(int,input().split()))
    tree = [ [ ] for _ in range(E+1+1)]
    
    for i in range(0,E*2,2):
        x=arr[i]
        y=arr[i+1]
        tree[x].append(y)
        
    cnt=0
    dfs(N)
    
    print(f'#{tc} {cnt}')

• 빈 []리스트를 여러 개 생성하고 싶을 경우 []*N이 아닌 for _ in range(N)을 사용한다.

아직 요령이 생기지 않은 Tree 단원이라 평소보다 시간이 걸렸다.