subtree Python(SW Expert Academy)

난이도 : D2

문제번호 : 5174

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVJ-_6qfsDFAWg

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

트리의 일부를 서브 트리라고 한다. 주어진 이진 트리에서 노드 N을 루트로 하는 서브 트리에 속한 노드의 개수를 알아내는 프로그램을 만드시오.   주어지는 트리는 부모와 자식 노드 번호 사이에 특별한 규칙이 없고, 부모가 없는 노드가 전체의 루트 노드가 된다. 이런 경우의 트리는 부모 노드를 인덱스로 다음과 같은 방법으로 나타낼 수 있다. 자식 노드가 0인 경우는 노드가 자식이 없는 경우이다.

입력

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50 다음 줄부터 테스트 케이스의 별로 첫 줄에 간선의 개수 E와 N이 주어지고, 다음 줄에 E개의 부모 자식 노드 번호 쌍이 주어진다. 노드 번호는 1번부터 E+1번까지 존재한다. 1<=E<=1000, 1<=N<=E+1

출력

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

예시

입력	출력
3 5 1 2 1 2 5 1 6 5 3 6 4 5 1 2 6 6 4 6 5 4 1 5 3 10 5 7 6 7 4 6 9 4 11 9 5 11 8 5 3 5 2 8 1 8 10	#1 3 #2 1 #3 3

---

2. 문제풀이

트리는 그래프의 서브셋이므로 그래프 풀이방법대로 푼다면 풀수가 있다. 단반향 그래프라고 생각하고 연결된 노드를 표시하는 리스트를 만든다. 재귀함수를 이용하여 출발노드부터 아래로 내려가며 하나씩 카운팅을 하게된다. 순회로 생각하면 전위순회라고 볼 수 있다.

---

3. 소스코드

# D2 5174 subtree
 
def dfs(idx):
    global count
    #순회를 할때마다 카운트
    count += 1
    #자식노드를 순회한다.
    for i in Tree[idx]:
        dfs(i)
 
for t in range(int(input())):
    #노드의 개수와 출력할 노드
    E, N = map(int, input().split())
    temp_list = input().split()
    #노드의 개수만큼 리스트 만들기
    Tree = [ [ ] for _ in range(E+2)]
    for idx, i in enumerate(range(0, E*2, 2)):
        a = int(temp_list[i])
        b = int(temp_list[i+1])
        #부모노드를 찾아서 자식노드 표현
        Tree[a].append(b)    
    count = 0
    dfs(N)
    #결과값 출력
    print('#{} {}'.format(t+1, count))