SWEA 5174サブツリー
問題のソースソフトウェアExpert Academy
問題の著作権は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
2 Dリストを再コンパイルとして作成する理由
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
Reference
この問題について(SWEA 5174サブツリー), 我々は、より多くの情報をここで見つけました https://velog.io/@wltn39/SWEA-5174-서브트리テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol