[프로그래머스] 모두 0으로 만들기

mokomoko·2022년 5월 14일
0

1. 문제


각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 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가 나타내는 그래프는 항상 트리로 주어집니다.

- 키워드

  • 트리의 특성을 잘 파악하도록 하자.

2. 풀이


표본이 300,000으로 상당히 커서 처음엔 이분탐색인가? 이런 생각을 했지만,

직관적인 트리문제였다.

트리를 구현하고, DFS를 이용해 전체 값을 계산하면 된다.

트리로 이 문제를 풀게 된다면, 어떤 노드를 루트로 잡아도 같은 결과가 나온다는 것이다.

표본이 크므로 DFS를 하기전에 depth 이슈를 미리 설정하도록 하자.

3. 소스코드


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]]))

4. 후기


사실 문제를 처음봤을 때 표본이 너무커서 트리로풀면 시간초과날거같다 생각해서

이진탐색으로 짱구를 굴려봤지만, 도저히 떠오르질 않았다.

검색해보니 트리문제 맞다고하니... 일단 내 생각을 그대로 해보는 것도 좋을 거같다.

0개의 댓글