[Programmers] Q76503 모두 0 으로 만들기

[Programmers] Q76503 모두 0으로 만들기

Question

Language: Python

이번 문제의 핵심 과제는 아래의 2가지이다.

1. Tree 구성
2. 가중치 전이과정

1. Tree 구성

Tree를 구성하는 경우에 대해서는, 0번 index을 root node로 설정해서 bfs 방식으로 자식 노드들을 추가한다.

visited=[False] * length
#Tree 구성
queue=deque([(0)])
visited[0]=True
while queue:
    vertex=queue.popleft()
    for adj_vertex in graph[vertex]:
        #이미 처리된 노드의 경우 넘어간다.
        if visited[adj_vertex]:
            continue
        visited[adj_vertex]=True
        #부모 정보를 할당한다.
        parents[adj_vertex]=vertex
        #tree에 추가한다.
        tree[vertex].append(adj_vertex) 
        queue.append(adj_vertex)

1. 가중치 전이 과정

전역변수로, cost, values을 활용한다. cost에서는 총 이동횟수를 저장하고, values에는 각각의 노드 값을 저장한다.

반환값의 부호를 정확하게 설정하는 것이 중요하다. 한쪽에서 빼고, 한쪽에서는 더하는 것이므로 자식 노드의 값을 반환할때는 음수 부호를 붙여서 반환한다.

def routing(tree,parents,vertex):
    global values,cost
    #leaf 노드가 아닌 경우에 대해서는 해당 노드의 자식 노드에 대한 전이과정을 먼저 수행한다.
    if len(tree[vertex])!=0:
        for adj_vertex in tree[vertex]:
            #자식 노드에 대한 이동 수행
            moving_value=routing(tree,parents,adj_vertex)
            #부모 노드로의 전이
            values[vertex]-=moving_value
            cost+=abs(moving_value)
            values[adj_vertex]=0

    return -values[vertex]

Solution

from collections import deque
import sys
values=[]
cost=0

def routing(tree,parents,vertex):
    global values,cost
    #leaf node인경우
    if len(tree[vertex])==0:
        return -values[vertex]
    for adj_vertex in tree[vertex]:
        #자식 노드에 대한 이동 수행
        moving_value=routing(tree,parents,adj_vertex)
        values[vertex]-=moving_value
        cost+=abs(moving_value)
        values[adj_vertex]=0
    #부모 노드로의 이동 수행
    return -values[vertex]

def solution(a, edges):
    sys.setrecursionlimit(300000)
    global values
    answer = 0
    
    #합이 0이 되지 않는 경우 --> 모든 노드를 0으로 만들 수 없음
    if sum(a) !=0:
        return -1
    
    length=len(a)
    graph=[[] for _ in range(length)]
    tree=[[] for _ in range(length)]
    parents=[-1] * length
    
    for v1,v2 in edges:
        graph[v1].append(v2)
        graph[v2].append(v1)
    visited=[False] * length
    
    #Tree 구성
    queue=deque([(0)])
    visited[0]=True
    while queue:
        vertex=queue.popleft()
        for adj_vertex in graph[vertex]:
            if visited[adj_vertex]:
                continue
            visited[adj_vertex]=True
            parents[adj_vertex]=vertex
            tree[vertex].append(adj_vertex) 
            queue.append(adj_vertex)
    
    #중간 노드가 가지는 값들의 합
    values=a
    routing(tree,parents,0)
    
    return cost if values[0]==0 else -1