🔎문제설명
각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 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가 나타내는 그래프는 항상 트리로 주어집니다.
🧊파이썬 코드
접근 방법
-
트리를 만들어줍니다.
-
트리를 만드는 과정에서 각 정점마다 간선의 갯수를 구해줍니다.
-
간선의 갯수가 하나인 정점들을 Queue에 넣어줍니다. (즉 leaf노드)
-
Queue에서 하나씩 빼와서 leaf노드와 연결된 정점에 가중치를 몰아줍니다.
-
leaf노드를 방문처리 합니다.
-
가중치를 몰아받은 정점의 간선의 개수를 줄여줍니다.
6-1. 만약 간선의 갯수가 1개가 되면 Queue에 넣어줍니다. -
Queue가 없을 때가지 반복합니다.
from collections import defaultdict
from collections import deque
def solution(a, edges):
answer = 0
tree = defaultdict(list);
idr = [0 for _ in a]
checked = [False for _ in a]
for edge in edges:
tree[edge[0]].append(edge[1]);
idr[edge[0]] += 1
tree[edge[1]].append(edge[0]);
idr[edge[1]] += 1
Q = deque()
#간선이 하나만 있는 리프노드들을 큐에 먼저 푸시
for i in range(len(a)):
if idr[i] == 1:
Q.append(i)
while Q:
node = Q.popleft();
checked[node] = True
for i in tree[node]:
#방문한 노드면 무시
if checked[i]:continue;
answer += abs(a[node])
a[i] += a[node]
a[node] = 0
idr[i] -= 1 #차수 줄이기
if idr[i] == 1:
Q.append(i)
return answer if sum(a) == 0 else -1저는 DFS로 풀다가 시간초과나서 포기하고 BFS로 바꿔서 풀었습니다..
다른사람은 DFS로도 풀었더군요..ㅠ
