◾ 모두 0으로 만들기 : 프로그래머스 LEVEL 3
문제
각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 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가 나타내는 그래프는 항상 트리로 주어집니다.
출력
- 트리의 모든 점들의 가중치를 0으로 만드는 것이 불가능하다면 -1을, 가능하다면 최소 몇 번만에 가능한지를 찾아 return
입출력 예
| 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. 해설
- 모든 노드가 루트가 될 수 있다는 것이 중요하다.
- DFS 또는 BFS를 통해 말단 노드부터 연산을 진행하여 최소 횟수를 구할 수 있다.
- 자식 노드의 값을 부모 노드의 값에 더해주며 진행한다.
- 이때, 연산 횟수는 절대값으로 만들어주어 계산한다.
- 0을 만들지 못하는 경우는
a의 합이 0이 아닌 경우이다.
2. 프로그램
a의 합이 0이 아닌 경우 -1 반환- {노드 번호 : 자식 노드}의 형태로 딕셔너리 생성
- 임의의 노드를 루트로 설정하여 DFS 탐색
- 말단 노드부터 연산을 진행하며 계산
# 코드
import sys
from collections import deque
sys.setrecursionlimit(300000)
answer = 0
def dfs(x, a, tree, visited):
global answer
# 현재 노드 탐색 표시
visited[x] = 1
for y in tree[x]:
# 탐색하지 않은 노드일 경우 연산 진행
if not visited[y]:
a[x] += dfs(y, a, tree, visited)
# 연산 횟수 추가
answer += abs(a[x])
# 현재 노드의 값 부모 노드로 전달
return a[x]
def solution(a, edges):
global answer
# 0을 만들 수 있는지 검사
if sum(a) != 0:
return -1
# 트리 생성
tree = {i : [] for i in range(len(a))}
# 각 노드의 자식 노드 추가
for u, v in edges:
tree[u].append(v)
tree[v].append(u)
# 방문 표시 리스트
visited = [0] * len(a)
# DFS 탐색
dfs(0, a, tree, visited)
# 결과 반환
return answer
후라이드 치킨