문제 설명 및 제한사항
문제 설명
각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다.
•
임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한쪽은 1 감소시킵니다.
하지만, 모든 트리가 위의 행동을 통하여 모든 점들의 가중치를 0으로 만들 수 있는 것은 아닙니다. 당신은 주어진 트리에 대해서 해당 사항이 가능한지 판별하고, 만약 가능하다면 최소한의 행동을 통하여 모든 점들의 가중치를 0으로 만들고자 합니다.
트리의 각 점의 가중치를 의미하는 1차원 정수 배열 a와 트리의 간선 정보를 의미하는 edges가 매개변수로 주어집니다. 주어진 행동을 통해 트리의 모든 점들의 가중치를 0으로 만드는 것이 불가능하다면 -1을, 가능하다면 최소 몇 번만에 가능한지를 찾아 return 하도록 solution 함수를 완성해주세요. (만약 처음부터 트리의 모든 정점의 가중치가 0이라면, 0을 return 해야 합니다.)
제한사항
•
a의 길이는 2 이상 300,000 이하입니다.
◦
a의 모든 수는 각각 -1,000,000 이상 1,000,000 이하입니다.
◦
a[i]는 i번 정점의 가중치를 의미합니다.
•
edges의 행의 개수는 (a의 길이 - 1)입니다.
◦
edges의 각 행은 [u, v] 2개의 정수로 이루어져 있으며, 이는 u번 정점과 v번 정점이 간선으로 연결되어 있음을 의미합니다.
◦
edges가 나타내는 그래프는 항상 트리로 주어집니다.
아이디어 및 해결 방법
두 점의 가중치를, 하나는 1 증가시키고 하나는 1 감소시키므로 연산 후에도 전체 트리의 가중치 합은 일정합니다.
따라서 ‘트리의 모든 노드의 가중치가 0이 될 수 있는가’의 여부는 ‘트리의 모든 노드의 가중치 합이 0인가’와 동치입니다.
우선 이 성질을 이용해서 불가능한지 여부를 판단 후 -1을 리턴하고… 더 생각해봅시다.
리프 노드의 입장에서 생각해보면, 자신의 가중치를 0으로 만드는 방법은 자신의 부모 노드로 자신의 가중치를 모두 전달하는 수 밖에 없습니다. 이 과정이 끝나면 리프 노드의 가중치는 0이 되고, 고려할 필요가 없어집니다. 그러면 리프 노드의 부모 노드를 새로운 리프 노드로 생각할 수 있고, 이 과정을 재귀적으로 반복해서 연산의 수를 구하면 될 것입니다.
자연스럽게 post-order traversal DFS를 쓰면 된다는 것을 알 수 있겠네요! Operation의 수는 자식 노드의 가중치의 절댓값이 된다는 것에 주의해서 연산의 수를 리턴하면 됩니다.
코드
from collections import defaultdict
import sys; sys.setrecursionlimit(10000000)
answer = 0
def solve(u, a, A, visited):
global answer
nops, val = 0, a[u]
for v in A[u]:
if v not in visited:
visited.add(v)
v, n = solve(v, a, A, visited)
val += v
nops += n + abs(v)
return val, nops
def solution(a, edges):
if all(x == 0 for x in a):
return 0
if sum(a) != 0:
return -1
A = defaultdict(list)
visited = set()
for u, v in edges:
A[u].append(v)
A[v].append(u)
visited.add(0)
return solve(0, a, A, visited)[1]
Python
복사
출처
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges