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

문제

• 각 점에 가중치가 부여된 트리가 주어질 때, 다음 연산으로 트리의 모든 점들의 가중치를 0으로 만들고자 한다.
  • 연산 : 임의의 연결된 두 점을 골라 한쪽은 1 증가시키고, 다른 한쪽은 1 감소시킨다.
• 주어진 트리에 대해 모든 점들의 가중치를 0으로 만들 수 있다면 최소 몇 번만에 가능한지 리턴하고, 불가능하다면 -1을 리턴한다.
•  2 <= 노드 개수 <= 300,000

 

풀이 1 (실패)

• 트리 형태이므로 부모-자식 간의 연산만 가능하다.
• 리프 노드부터 0으로 만들기 시작하면 되지 않을까?
  
  • 리프 노드 = 그래프 간선이 1개 밖에 없는 노드

실패 (6cases)

모든 리프 노드에서부터 시작하기 때문에 visited 확인에 있어서, 중간에 노드가 겹치는 일이 발생하는 일이 아닌가 싶다. 예를 들어 1개의 리프 노드에서 루트 노드까지 뻗어나온 경우 루트 노드가 True 가 되면서, 다른 리프 노드에서 루트 노드로 갈 때 연산이 이뤄지지 않는 것이다.

from collections import deque

def solution(a, edges):
    if sum(a) != 0 :		# 0으로 만들 수 없는 경우
        return -1

    n = len(a)
    graph = [[] for _ in range(n)]
    for s, e in edges :
        graph[s].append(e)
        graph[e].append(s)
    
    
    q = deque()
    for i in range(n) :         # 리프 노드 추가하기
        if len(graph[i]) == 1 :
            q.append(i)

    answer = 0
    visited = [False] * n
    while q :
        now = q.popleft()       # 현재 노드
        if visited[now] :       # 이미 처리된 노드면 pass
            continue
        visited[now] = True     # 방문 처리
        
        for p in graph[now] :   # 처리되지 않은 연결된 노드들 중에서
            if visited[p] : continue
            answer += abs(a[now])   # 현재 노드 0으로 만들기
            a[p] += a[now]
            a[now] = 0
            q.append(p)
                
    return answer

 

 

테스트 1 〉	통과 (0.00ms, 10.2MB)
테스트 2 〉	통과 (0.01ms, 10.3MB)
테스트 3 〉	통과 (3.54ms, 69.8MB)
테스트 4 〉	실패 (819.69ms, 105MB)
테스트 5 〉	실패 (848.24ms, 105MB)
테스트 6 〉	통과 (3.89ms, 70MB)
테스트 7 〉	통과 (730.85ms, 99.5MB)
테스트 8 〉	통과 (704.74ms, 99.5MB)
테스트 9 〉	통과 (3.58ms, 70MB)
테스트 10 〉	실패 (868.61ms, 112MB)
테스트 11 〉	실패 (887.80ms, 104MB)
테스트 12 〉	통과 (3.64ms, 69.9MB)
테스트 13 〉	통과 (642.98ms, 112MB)
테스트 14 〉	통과 (618.54ms, 112MB)
테스트 15 〉	통과 (3.49ms, 70MB)
테스트 16 〉	실패 (768.78ms, 104MB)
테스트 17 〉	실패 (716.86ms, 110MB)
테스트 18 〉	통과 (432.21ms, 112MB)

 

풀이 2

• dfs를 통해 루트~리프까지의 경로에서 값을 루트 노드로 쭉 전달한다.
  • 현재 노드의 자식 노드로 이동한다. (parent 는 무시한다.)
  • 리프 노드에서부터 루트 노드까지 쭉 0으로 만드는 연산을 백트래킹 한다.

 

import sys
sys.setrecursionlimit(10**6)
answer = 0

def dfs(now, parent, graph, a) :
        global answer
        # 현재 노드 now의 자식노드로 이동 (depth 우선 탐색)
        for c in graph[now] :
            if c != parent :
                dfs(c, now, graph, a)
        # 현재 노드 0으로 만들기
        a[parent] += a[now]
        answer += abs(a[now])

def solution(a, edges):
    if sum(a) != 0 :            # 0으로 만들 수 없는 경우
        return -1

    n = len(a)
    graph = [[] for _ in range(n)]
    for s, e in edges :
        graph[s].append(e)
        graph[e].append(s)
        
    dfs(0, 0, graph, a)      
    return answer

 

References

• 프로그래머스 Lv3 모두 0으로 만들기
• Deeppago / 모두 0으로 만들기