[SWEA][Python3] 1248. [S/W 문제해결 응용] 3일차 - 공통조상
2019.05.18 00:24
|
프로그래밍/삼성 SWEA
나의 풀이 :
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def find_LCA(root, p, q):
if root in (p, q, None):
return root
left = find_LCA(root.left, p, q)
right = find_LCA(root.right, p, q)
return root if (left and right) else (left or right)
def count_children(root):
if root:
left = count_children(root.left)
right = count_children(root.right)
return 1 + left + right
return 0
T = int(input())
for tc in range(1, T + 1):
V, E, P, Q = map(int, input().split())
nodes = [Node(x) for x in range(V+1)]
edges = list(map(int, input().split()))
for i in range(0, 2*E, 2):
parent = nodes[edges[i]]
child = nodes[edges[i+1]]
if not parent.left:
parent.left = child
else:
parent.right = child
lca = find_LCA(nodes[1], nodes[P], nodes[Q])
count = count_children(lca)
print('#{} {} {}'.format(tc, lca.val, count))
한마디 :
LCA를 찾는 작업과 트리의 크기를 구하는 작업을 별도로 수행했는데, 최적의 방법인지는 잘 모르겠다.
'프로그래밍 > 삼성 SWEA' 카테고리의 다른 글
| [SWEA][Python3] 1248. [S/W 문제해결 응용] 3일차 - 공통조상 (0) | 2019.05.18 |
|---|---|
| [SWEA][Python3] 1245. [S/W 문제해결 응용] 2일차 - 균형점 (0) | 2019.05.17 |
| [SWEA][Python3] 1849. 영준이의 무게측정 (0) | 2019.05.16 |
| [SWEA][Python3] 1247. [S/W 문제해결 응용] 3일차 - 최적 경로 (0) | 2019.05.09 |
| [SWEA][Python3] 5357. 터널 속의 기차 (0) | 2019.05.02 |
