모두 0으로 만들기 [자바]

 

🧫 문제 분석

✔️ 출처

모두 0으로 만들기 level 3

📖 문제

 

dfs로 푸니 메모리 제한사항이 빡빡해서 6,7번에서 런타임 예외 (stackoverflow)가 터졌다.

변수를 static으로 선언, iterator를 사용하지 않는 일반for문 사용

 

우선 트리에서 가중치가 가장 작은 노드를 기준으로

DFS 탐색해서 리프노드부터 값을 넘기면서 연산 횟수를 카운팅하면된다.

 

그리고 특정 상황 즉, 모두 0이거나, 불가능한 경우는 미리 처리한다.

 a의 모든 합이 0이 아니면 절대로 모든 정점의 가중치를 0으로 만들 수 없으므로 바로 -1 반환

 a의 모든 요소가 0이면 0 반환

 

 

재귀를 통한 dfs 말고 

stack으로 dfs를 구현하면 더 안정적일 것 같다. 

 

---

🔅 문제 풀이

import java.util.*;

class Solution {
    static List<Integer>[] trees;
    static boolean[] visited;
    static long cnt = 0;
    static int[] oa;
    
    public long solution(int[] a, int[][] edges) {
        oa = a;
        
        // 트리 생성
        trees = new ArrayList[a.length];
        for (int i = 0; i < trees.length; i++) {
            trees[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0];
            int v = edges[i][1];
            trees[u].add(v);
            trees[v].add(u);
        }
        
        
        // a의 합이 0인지 검증
        long rs = 0;
        int prev = 0, min = 0, idx = 0;
        boolean isInitAllZero = true; // 전부 0인지 체크
        
        for (int i = 0; i < a.length; i++) {
            if (prev != a[i]) isInitAllZero = false;
            
            // 최소값을 가지는 idx 기록
            if (min > a[i]) {
                min = a[i];
                idx = i;
            }
            
            rs += a[i];
        }
        
        if (isInitAllZero) return 0;
        // 0이 아니라면 만들기 불가능
        if (rs != 0) return -1;
        
        
        // 최소 값의 트리를 채우는 것을 목표로 최소 값 노드를 기준으로 탐색
        // + 인 애들껄 뺏어서 채워나가는 식
        visited = new boolean[a.length + 1];
        visited[idx] = true;
        dfs(idx);
        
        return cnt;
    }
    
    private long dfs(int idx) {
        long sum = 0;
       
        for (int i = 0; i < trees[idx].size(); i++) {
            int next = trees[idx].get(i);
            
            if (!visited[next]) {
                visited[next] = true;
                sum += dfs(next);
            }
        }
        
        // 현재 노드의 가중치를 0으로 만들고 가중치를 반환
        sum += oa[idx];
        cnt += Math.abs(sum);
        oa[idx] = 0;
        
        return sum;
    }
}

 

❗ 오답노트 / 필요한 지식