각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다.
임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한쪽은 1 감소시킵니다.
하지만, 모든 트리가 위의 행동을 통하여 모든 점들의 가중치를 0으로 만들 수 있는 것은 아닙니다. 당신은 주어진 트리에 대해서 해당 사항이 가능한지 판별하고, 만약 가능하다면 최소한의 행동을 통하여 모든 점들의 가중치를 0으로 만들고자 합니다.
트리의 각 점의 가중치를 의미하는 1차원 정수 배열 a와 트리의 간선 정보를 의미하는 edges가 매개변수로 주어집니다. 주어진 행동을 통해 트리의 모든 점들의 가중치를 0으로 만드는 것이 불가능하다면 -1을, 가능하다면 최소 몇 번만에 가능한지를 찾아 return 하도록 solution 함수를 완성해주세요. (만약 처음부터 트리의 모든 정점의 가중치가 0이라면, 0을 return 해야 합니다.)
- 트리의 특성을 잘 파악하도록 하자.
표본이 300,000으로 상당히 커서 처음엔 이분탐색인가? 이런 생각을 했지만,
직관적인 트리문제였다.
트리를 구현하고, DFS를 이용해 전체 값을 계산하면 된다.
트리로 이 문제를 풀게 된다면, 어떤 노드를 루트로 잡아도 같은 결과가 나온다는 것이다.
표본이 크므로 DFS를 하기전에 depth 이슈를 미리 설정하도록 하자.
import sys
sys.setrecursionlimit(300001)
counter = [0] * 300001
result = 0
def search(a,tree,before,now):
counter[now] = 1
global result
for i in tree[now]:
if counter[i] == 0:
search(a,tree,now,i)
if before != -1:
a[before] += a[now]
result += abs(a[now])
def solution(a,edges):
tree = dict()
for i in range(len(a)):
tree[i] = []
for edge in edges:
start,end = edge
tree[start].append(end)
tree[end].append(start)
search(a,tree,-1,0)
if a[0] == 0:
return result
else:
return -1
if __name__ == "__main__":
print(solution([-5,0,2,1,2],[[0,1],[3,4],[2,3],[0,3]]))
사실 문제를 처음봤을 때 표본이 너무커서 트리로풀면 시간초과날거같다 생각해서
이진탐색으로 짱구를 굴려봤지만, 도저히 떠오르질 않았다.
검색해보니 트리문제 맞다고하니... 일단 내 생각을 그대로 해보는 것도 좋을 거같다.