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

트리

📌 문제출처 https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVJ-_6qfsDFAWg   트리 노드 용어 정리 http://www.ktword.co.kr/abbr_view.php?m_temp1=4726

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

 

트리의 일부를 <<서브 트리>>라고 한다.

주어진 이진 트리에서 노드 N을 루트로 하는 서브 트리에 속한 노드의 개수를 알아내는 프로그램을 만드시오.

주어지는 트리는 부모와 자식 노드 번호 사이에 특별한 규칙이 없고,

부모가 없는 노드가 전체의 루트 노드가 된다.

이런 경우의 트리는 부모 노드를 인덱스로 다음과 같은 방법으로 나타낼 수 있다.

자식 노드가 0인 경우는 노드가 자식이 없는 경우이다.

부모	1	2	3	4	5	6
자식1( left )	6	1	0	0	3	4
자식2 ( right )	0	5	0	0	0	0

[입력]

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50
다음 줄부터 테스트 케이스의 별로 첫 줄에 간선의 개수 E와 N이 주어지고,

다음 줄에 E개의 부모 자식 - 노드 번호 쌍이 주어진다.
노드 번호는 1번부터 E+1번까지 존재한다. 1<=E<=1000, 1<=N<=E+1

[출력]

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

 

---

✍ [문제 간략 해석]

 

부모가 없는 노드가 전체의 루트 노드

부모 노드를 인덱스로 나타낼 수 있다.

자식 노드가 0인 경우는 노드가 자식이 없는 경우

 

[입력]

첫 줄에 간선의 개수 E와, 서브트리의 루트 번호 N이 주어지고,

다음 줄에 E개의 (부모 자식-노드 번호) 쌍이 주어진다. (E*2개)

노드 번호는 1번부터 E+1번까지 존재한다.

1<=E<=1000, 1<=N<=E+1

 

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

 

[출력]

이진 트리에서 노드 N을 루트로 하는

서브 트리에 속한 노드의 개수를 알아내기

답 : 1 ~ E+1

#1 3

#2 1

#3 3

 

💡 PASS

[파이썬 코드]

 

# # 5174. [파이썬 S/W 문제해결 기본] 8일차 - subtree D2
# 구현3
def inorder(node): 
    global cnt
    if node == 0:
        return
    # 전위
    cnt += 1
    inorder(left[node])
    # 중위
    inorder(right[node])
    # 후위
 
for test_case in range(1, int(input()) + 1):
    E,N = map(int, input().split())
    arr = list(map(int, input().split()))
    # 구현1
    left = [0]*(E+2) # 첫번째 자식
    right = [0]*(E+2) # 두번째 자식
    # 구현2
    for i in range(0,len(arr),2): 
        papa, baby = arr[i], arr[i+1] # 부모 - 자식
        if left[papa]: # 0이 아니고 첫번째에 값이 있으면
            right[papa]=baby # 두번째에 보관
        else: # 0이면
            left[papa]=baby # 첫번째에 보관
 
    cnt = 0
    inorder(N)
    print('#{} {}'.format(test_case,cnt))
 

 

 

✍ [풀이방법]

 

1. 부모-자식 쌍에서, 자식을 좌/우 (첫번째/두번째) 로 나눈 각각 배열을 만든다

노드의 수 N, (두 노드끼리 연결하는) 간선의 수 N-1 (루트노드는 부모가 없기 때문에)  노드의 수 = 간선의 수 + 1  간선의 수 = 노드의 수 - 1

노드들은 1부터 N번까지 세므로, index 0 부터 시작하므로, 노드의 수+1(간선의 수 +2)해줘서 배열 만들기

 

2. 0으로 초기화 된 배열에 인덱스 번호를 통해서, 0이 아니면 값을 넣어주기

부모 (인덱스번호)	0	1	2	3	4	5	6
자식1( left )	0	6	1	0	0	3	4
자식2 ( right )	0	0	5	0	0	0	0

 

3. 순회하기

전위순회	루트 - 좌 - 우
중위순회	좌 - 루트 - 우
후위순회	좌 - 우 - 루트

    def inorder(node):
        if node == 0:
            return
        # 전위 1 6 4
        #print(node, end=',')
        inorder(left[node])
        # 중위 4 6 1
        #print(node, end='-')
        inorder(right[node])
        # 후위 4 6 1
        #print(node, end=':')
 
    inorder(N) # N이 루트 노드 일 때, 전부 순회
 

순서 상관없이 개수만 세면 되서 아무대나 카운트를 해줬다.