모두 0으로 만들기

2025-10-15

#JAVA#프로그래머스

2분

문제 링크

문제 풀이 시간 : 59분

문제 요약

•
각 노드에 가중치가 있고, 간선으로 연결된 트리가 주어진다.

•
한 번의 연산으로 두 노드 간의 값을 주고받을 수 있다.

•
모든 노드의 가중치를 0으로 만드는 데 필요한 최소 연산 횟수를 구하는 문제.

•
단, 모든 노드의 합이 0이 아니라면 어떤 방식으로도 0으로 만들 수 없으므로 1을 반환

문제 풀이

이 문제는 처음 봤을 때,

먼저 모든 노드의 가중치 합이 0이 되는지 확인해야 한다는 생각이 들었다.

왜냐하면 전체 합이 0이 아니라면,

아무리 값을 옮겨도 총합은 변하지 않기 때문이다.

즉, 합이 0이 아닌 경우에는 절대 모든 노드를 0으로 만들 수 없다.

그래서 다음과 같이 접근했다:

•
a 배열의 모든 값을 더해서 sum != 0이면 바로 -1을 반환한다.

•
만약 합이 0이라면, 리프 노드부터 차근차근 값을 부모에게 전달하면서 0으로 만든다.

리프 노드는 더 이상 자식이 없기 때문에, 그 값을 부모에게 넘기면 리프 노드는 0이 되고 제거할 수 있다.

이후 부모의 차수를 하나 줄여주고, 차수가 1이 된 부모 노드를 새로운 리프 노드로 큐에 추가한다.

이 과정을 반복하면, 결국 트리의 루트까지 도달하면서

모든 노드의 가중치를 0으로 만들 수 있다.

하지만 처음 이 로직을 구현했을 때 일부 테스트 케이스가 실패했다.

이유를 찾지 못해서 GPT에게 물어봤고, 문제는 오버플로였다.

가중치의 범위가 ±10⁹이기 때문에,

값을 여러 번 더하고 빼는 과정에서 int 범위를 초과하는 경우가 발생했던 것이다.

따라서 다음과 같이 수정했다:

•
a 배열을 그대로 사용하지 않고,
long[] w 배열을 새로 만들어 long 타입으로 계산한다.

풀이 과정 정리

1
합 검증 (sum != 0)
- •
  전체 노드의 가중치 합이 0이 아니면 즉시 -1을 반환한다.

2
그래프 구성
- •
  인접 리스트와 각 노드의 차수를 초기화한다.
- •
  트리이므로 간선을 양방향으로 저장한다.

3
리프 노드 큐 초기화
- •
  차수가 1인 노드를 모두 큐에 넣는다.
- •
  이후 이 큐를 이용해 리프부터 부모로 값을 전달한다.

4
BFS 방식으로 처리
- •
  큐에서 리프 노드를 하나씩 꺼낸다.
- •
  해당 노드의 값을 부모에게 더하고, 자신의 값은 0으로 만든다.
- •
  부모의 차수를 1 줄이고, 새 리프가 되면 큐에 추가한다.
- •
  이동한 값의 절댓값을 answer에 더해 전체 이동 횟수를 누적한다.

5
결과 반환
- •
  모든 노드의 가중치를 0으로 만들 수 있다면, 누적된 answer를 반환한다.

최종 코드

Java

import java.util.*;

class Solution {
    public long solution(int[] a, int[][] edges) {
        long answer = 0;
        int n = a.length;
        long sum = 0;
        long[] w = new long[n]; // 노드 가중치를 long으로 저장
        int[] degree = new int[n]; // 각 노드의 차수
        
        // 전체 합 계산 및 long 배열 초기화
        for(int i=0;i<n;i++){
            sum += a[i];
            w[i] = a[i];
        }
        
        // 합이 0이 아니면 불가능
        if(sum!=0)
            return -1;
        
        List<Integer>[] tree = new ArrayList[n];
        for(int i=0;i<n;i++)
            tree[i] = new ArrayList<>();
        
        // 간선 정보 저장
        for(int i=0;i<edges.length;i++){
            int c = edges[i][0];
            int b = edges[i][1];
            tree[c].add(b);
            tree[b].add(c);
            degree[c]++;
            degree[b]++;
        }
        
        // 리프 노드부터 시작
        Queue<Integer> leaf = new ArrayDeque<>();
        for(int i=0;i<n;i++){
            if(degree[i]==1)
                leaf.add(i);
        }
        
        boolean[] visited = new boolean[n];
        
        // 리프부터 차근차근 부모 방향으로 값 전달
        while(!leaf.isEmpty()){
            int now = leaf.poll(); // 현재 리프 노드
            long val = w[now]; // 현재 노드의 가중치
            w[now] = 0; // 현재 노드는 0으로 만들기
            visited[now] = true;
            answer += Math.abs(val); // 이동한 절댓값 누적
            
            // 연결된 부모 노드에 값 전달
            for(int next : tree[now]){
                if(!visited[next]){
                    w[next] += val; // 부모에 현재 값 더하기
                    degree[next]--; // 부모 차수 감소
                    if(degree[next]==1) // 새 리프가 되면 큐에 추가
                        leaf.add(next);
                }
            }
        }
        
        return answer;
    }
}