[Programmers] 모두 0으로 만들기 바로가기
각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다.
트리의 각 점의 가중치를 의미하는 1차원 정수 배열 a
와 트리의 간선 정보를 의미하는 edges
가 매개변수로 주어집니다. 주어진 행동을 통해 트리의 모든 점들의 가중치를 0으로 만드는 것이 불가능하다면 -1을, 가능하다면 최소 몇 번만에 가능한지를 찾아 return 하도록 solution 함수를 완성해주세요. (만약 처음부터 트리의 모든 정점의 가중치가 0이라면, 0을 return 해야 합니다.)
a[i]
는 i번 정점의 가중치를 의미합니다.[u, v]
2개의 정수로 이루어져 있으며, 이는 u번 정점과 v번 정점이 간선으로 연결되어 있음을 의미합니다.a | edges | result |
---|---|---|
[-5,0,2,1,2] | [[0,1],[3,4],[2,3],[0,3]] | 9 |
[0,1,0] | [[0,1],[1,2]] | -1 |
입출력 예 #1
입출력 예 #2
2
→ 4
→ 3
→ 0
→ 1
의 순서에 따라 진행되었다.1
을 기준으로 후위 순회(post order
) 의 순서가 적용된다는 것을 알 수 있다.def postOrder(n):
global answer
for i in graph[n]:
if visited[i]:
visited[i] = False
a[n] += postOrder(i)
answer += abs(a[n])
return a[n]
n
)에 연결된 모든 정점(i
)을 재귀의 방식을 통해 방문한다. answer
에는 현재 정점의 가중치 값을 누적으로 더한다.graph = defaultdict(list)
headCandidate = defaultdict(int)
for n1, n2 in edges:
graph[n1].append(n2)
graph[n2].append(n1)
headCandidate[n1] += 1
headCandidate[n2] += 1
edges
)를 통해 그래프(graph
)를 생성한다.headCandidate
는 헤드 노드의 정보를 얻기 위해 선언한 자료구조이다.edges
)를 통해 각 정점에 연결된 간선의 개수를 카운트할 수 있다.for key, value in headCandidate.items():
if value == 1:
head = key
break
head
)로 선정한다.visited = [True] * len(a)
visited[head] = False
postOrder(head)
head
)를 이용하여 후위 순회 방식을 통해 그래프를 탐색한다.visited
리스트를 선언한다.from sys import setrecursionlimit
from collections import defaultdict
setrecursionlimit(10**6) # 재귀 깊이 제한 해제
answer = 0
def solution(a, edges):
def postOrder(n):
global answer
for i in graph[n]:
if visited[i]:
visited[i] = False
a[n] += postOrder(i)
answer += abs(a[n])
return a[n]
# 그래프 생성
graph = defaultdict(list)
headCandidate = defaultdict(int)
for n1, n2 in edges:
graph[n1].append(n2)
graph[n2].append(n1)
headCandidate[n1] += 1
headCandidate[n2] += 1
# head node 찾기
for key, value in headCandidate.items():
if value == 1:
head = key
break
# post order
visited = [True] * len(a)
visited[head] = False
postOrder(head)
return answer if a[head] == 0 else -1