SWEA 5174 서브트리

문제출처 SW Expert Academy
문제의 저작권은 SW Expert Academy에 있습니다.

문제소개

노드 N을 루트로 하는 서브트리의 노드 개수를 출력하는 프로그램 작성하시오.
간선의 갯수는 E개이며, 노드번호는 1부터 E+1번까지 존재한다. 

입력:
1
5 1 (간선 E, 루트노드 N)
2 1 2 5 1 6 5 3 6 4 (예 : 부모-자식 노드)

출력:
#1 3 (1을 루트노드로 하는 서브트리는 1, 6, 4의 3개 노드로 구성)  

풀이접근

- 2차원 배열로 2차원 트리모양 표시
- 서브트리의 간선 개수 +1을 하면 노드 개수 나옴

코드

# 입력된 tree에 종속되는 sub_tree의 함수 작성
def sub_tree(idx):
    global count # 서브트리 노드 개수 count
    
    # 노드의 자식노드 좌우검사 (0을 좌, 1을 우로 설정)
    for i in range(2):
        if tree[i][idx]: # 좌 or 우에 값이 있으면
            count += 1 # 서브트리 노드갯수 1 증가 
            # 현재 tree노드값을 대입해 다음 세대확인 
            n = tree[i][idx]
            sub_tree(n)

for tc in range(1, int(input()) + 1):
    E, N = map(int, input().split()) # 간선갯수 E, 서브트리루트노드 N 
    temp = input().split() # 부모-자식 노드 입력받기 
    
    # 좌우에 있는 자식을 표현하기 위한 2차원 리스트
    tree = [[0 for _ in range(E+2)]for _ in range(2)]
    
    for i in range(E): 
        idx = int(temp[2*i]) # tree 부모노드
        number = int(temp[2*i+1]) # tree 자식노드
        # 값이 없으면 좌측에 number 대입 
        if tree[0][idx] == 0:
            tree[0][idx] = number
        # 값이 있으면 우측에 number 대입
        else:
            tree[1][idx] = number
            
    count = 1 # 루트노드도 카운트되니 1부터 시작
    sub_tree(N) # N부터 실행 
        
    print(f'#{tc} {count}')

 1
 5 1
 2 1 2 5 1 6 5 3 6 4


#1 3

정의된 변수 값 확인

temp

['2', '1', '2', '5', '1', '6', '5', '3', '6', '4']

tree

[[0, 6, 1, 0, 0, 3, 4], [0, 0, 5, 0, 0, 0, 0]]

print(idx, number)

6 4

count = 0
sub_tree(6)
count

1

count = 0
sub_tree(3)
count

0

이차원리스트를 리스리컴프리헨션으로 만들어야 하는 이유

• 깊은 복사 vs 얕은 복사

arr = [[0] * 5] * 5 
arr[0][0] = 5 # 얕은 복사(주소값 복사)로 뒤쪽 0번 인덱스는 모두 5로 대입됨
arr[1][0]

5

arr = [[0 for col in range(4)] for row in range(3)]
arr[0][0] = 5 # 깊은 복사(실제 값을 새로운 메모리에 복사)로 원하는 위치만 바뀜
arr[1][0]

0