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
Author And Source
이 문제에 관하여(SWEA 5174 서브트리), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@wltn39/SWEA-5174-서브트리저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)