프로그래머스 모두 0으로 만들기 (python, 파이썬)

• 문제

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

---

• 입/출력

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

---

• 코드

import sys
sys.setrecursionlimit(300000)

def dfs(x, a, board):
    global visited
    global answer
    global length
    
    now = a[x]
    visited[x] = 1
    
    for i in board[x]:
        if visited[i] == 0:
            now += dfs(i, a, board)
            
    answer += abs(now)
    
    return now
    
def solution(a, edges):
    global visited
    global answer
    global length
    
    answer = 0
    
    if sum(a) != 0:
        return -1
    
    length = len(a)
    board = [[] for _ in range(length)]

    for i, j in edges:
        board[i].append(j)
        board[j].append(i)
    
    visited = [0]*length
    dfs(0, a, board)
    return answer

board에 그 다음으로 이동할수있는 edge를 담아준다.

visited배열은 방문여부를 확인한다.

 

실제로 처음 문제를 풀때 dfs로는 생각을 했는데 그래프문제에 약해서 더 이상 생각하지 못했다..

정말 코드가 간단했다... dfs를 진행하면서 값에 추가시켜준다는 개념을 하는 방법을 새로 배운것같다...!! 

자세한 내용은 그림의 나온 숫자를 따라가면서 진행해주면됩니다.

 

큰 틀은 dfs가 끝나면 answer에 값을 추가시키고 dfs를 진행하는동안 값을 계속 처음 시작한 노드에 추가시켜주는것이다. 그 이유는 하나의 값을 0으로 만들어야하기 때문이다. 즉 -1이랑 2가 연결되어있다면 -1이 끝노드이면 이 값을 없애주는데 answer1을 추가하고 0이랑 3으로 바뀌니까 3으로 계속 진행하는것이다.!

---

• 출처

programmers.co.kr/learn/courses/30/lessons/76503?language=python3