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

풀이 방법

주어진 행동을 통해 트리의 모든 점들의 가중치를 0으로 만드는 것이 불가능하다면 -1을, 가능하다면 최소 몇 번만에 가능한지를 찾아 return 하세요.

 

어떻게 탐색을 해야 트리의 모든 점들의 가중치를 0으로는 만드는 과정을 최소화 할 수 있을까요?

 

결론부터 이야기 하자면, DFS의 후위 순회 탐색을 하면 됩니다.

 

왜 DFS의 후위 순회 탐색을 해야 할까요?

 

먼저 DFS의 후위 순회 탐색을 하지 않은 경우를 보겠습니다.

그래프의 모양은 아래와 같고, 후위 순회가 아닌 전위 순회를 해보겠습니다.

 

전위 순회는 현재 노드를 처리한 후 자식 노드를 탐색하는 방식입니다.

0번 노드를 0으로 만들기 위해선 1번 노드와 3번 노드의 값을 조절하여 0번 노드를 0으로 만들어야 합니다.

3번 노드에 5를 빼고, 0번 노드에 5를 더해서 0번 노드를 0으로 만들었다고 칩니다.

 

3번 노드는 현재 -4라는 값이 됩니다. 3번 노드가 부모 노드일땐, 자식 노드 4번과 2번이 있습니다.

3번 노드를 0으로 만들기 위해서 2번 노드와 4번 노드의 값을 조절해야 합니다.

 

4번 노드의 값을 조절한다고 가정하고, 4번 노드의 값에 +4를 해줍니다.

3번노드는 0이 되고, 4번 노드는 8이 되었습니다.

 

하지만, 이 문제는 모든 노드를 0으로 만드는 것입니다.

4번 노드를 0으로 만들기 위해선 다시 8을 빼주고, 부모 노드인 3번 노드에 8을 더해주어야 합니다.

 

즉, 부모 노드를 먼저 갱신하는 경우 자식 노드를 갱신할 때, 부모 노드를 한번 더 갱신해야 된다는 문제점이 있습니다.

이는 최소 횟수 보장이 되지 않음을 의미합니다.

 

후위 순회를 하면 어떻게 될까요?

 

후위 순회를 하기 위해서 리프 노드까지 탐색을 합니다.

 

4번 노드가 최하단이므로, 4번 노드에서 2를 빼고, 3번노드에 2를 더합니다.

4번 노드는 0이 되고, 3번 노드는 3이 됩니다.

 

다음으로 2번 노드에서 2를 빼고, 3번 노드에서 2를 더합니다.

2번 노드는 0이 되고, 3번 노드는 5가 됩니다.

 

3번 노드는 현재 5이기 때문에, 3번 노드에서 5를 빼고 0번 노드에 5를 더합니다.

3번 노드는 0이 되고, 0번 노드도 0이 됩니다.

 

1번 노드는 현재 0이므로 아무것도 해주지 않습니다.

모든 정점이 0이 되었습니다.

 

DFS 후위 순회를 하는 경우엔 이전 전위 순회를 할때처럼 부모 노드를 한번 더 갱신하지 않아도 됩니다.

자식 노드에서 부모 노드로 가중치를 가져 오는 방식이므로 한번만 갱신해주면 됩니다.

즉, 최소 행동으로 모든 노드를 0으로 만들 수 있게 됩니다.

 

DFS로 후위 순회를 어떻게 구현할까요?

 

구현한 코드는 다음과 같습니다.

import java.util.*;

class Solution {

    private long totalMove = 0;
    private List<Integer>[] graph;
    private boolean[] visited;
    
    public long solution(int[] a, int[][] edges) {
        long sum = 0;
        
        for(int i = 0; i < a.length; i++) {
            sum += a[i];
        }
        
        if(sum != 0) return -1; // 전부 더한 경우 0이 되야 가능
        
        
        int n = a.length;
        
        graph = new ArrayList[n];
        visited = new boolean[n];
        
        for(int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        
        for(int i = 0; i < edges.length; i++) {
            int[] edge = edges[i];
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }
        
        dfs(0, a);
        
        return totalMove;
    }
    
    private long dfs(int curNode, int[] a) {
        visited[curNode] = true;
        long weight = a[curNode];
        
        for(int i = 0; i < graph[curNode].size(); i++) {
            int next = graph[curNode].get(i);
            
            if(!visited[next]) {
                weight += dfs(next, a);
            }
        }
        
        totalMove += Math.abs(weight);
        return weight;
    }
}

 

DFS 부분을 보겠습니다.

private long dfs(int curNode, int[] a) {
        visited[curNode] = true;
        long weight = a[curNode];
        
        for(int i = 0; i < graph[curNode].size(); i++) {
            int next = graph[curNode].get(i);
            
            if(!visited[next]) {
                weight += dfs(next, a);
            }
        }
        
        totalMove += Math.abs(weight);
        return weight;
    }

 

DFS의 반환값에 weight(가중치)를 더해줌으로써, 리프 노드까지 깊이 파고든 후, 리프 노드부터 순차적으로 필요한 연산 횟수를 부모 노드까지 전달하는 방식으로 구현합니다. 즉, DFS 후위 순회를 수행하게 됩니다.

 

출력 결과