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

https://school.programmers.co.kr/learn/courses/30/lessons/76503

프로그래머스

코딩테스트 연습 > 월간 코드 챌린지 시즌2 > 모두 0으로 만들기

 

난이도: LEVEL3

알고리즘 유형:  여러가지 그래프 탐색 

풀이 설명

트리 문제이다. 

해당 트리는 이진 트리가 아니다.

트리의 특징은 어떤 정점을 루트 노드로 잡아도 트리 모양이다. 

 

0번 정점을 루트 노드로 잡고 다른 노드들의 level을 구한다.

루트 노드인 0번 정점은 level 1 

다른 노드의 level을 구하는 방식은 dfs 메소드를 사용해서 구했다.

level을 구하면서 추가적으로 현재 노드의 간선이 1개 밖에없고 유일한 간선의 반대 노드가 해당 노드의 level 보다 낮다면 현재 노드는 리프 노드(제일 마지막 노드)이다. 

해당 리프 노드들을 큐에 넣어준다. 

또한 자식 정점의 개수를 child 배열에 누적한다. 

나중에 위상정렬에 사용한다. 

 

현재 큐에 들어간 노드들은 리프 노드이다. 

노드에 있는 값을 answer에 추가한다. - 면 양수로 바꿔서 더한다. 

노드에 있는 값을 부모 노드에 더하고 현재 노드를 0으로 바꿔준다. 

child 배열의 현재 노드 부모 노드 인덱스를 하나 줄인다. 

만약 child[i]가 0이라면 부모 노드를 큐에 추가한다.

 

이렇게 하는 이유는 

만약 매번 부모 노드를 넣어준다면

큐에 중복된 부모 노드가 계속 들어가게 되고 

똑같은 경로의 계산이 반복되어서 시간 초과가 발생할 것이다. 

 

내가 실수한 부분 

위상 정렬을 사용하지 않아서 3개 케이스의 시간 초과

각 노드의 값을 저장하는 a 배열을 그대로 사용해서 많은 케이스가 틀렸다.

각 노드의 값은 초기는 int 범위지만 계산을 하다 보면 long으로 넘어가는 케이스가 있다.

 

각 배열의 범위는 - 1,000,000 * 300,000  <= 배열 범위 <=  1,000,000 * 300,000 

그래서 long으로 새로운 배열을 선언하고 기존 값을 복사해서 시작해야 한다.  

정답 코드 

import java.util.*;
class Solution {
    static int size;
    static ArrayList<Integer> [] graph;  // 그래프 
    static int [] level; // 각 정점의 레벨 기록 
    static int max_level = 1;
    static int [] child; // 자식의 개수 저장
    // 리프 노드들 저장 리스트 
    static Queue<Integer> list = new LinkedList<>();
    public long solution(int[] a, int[][] edges) {
        long answer = 0;
        size = a.length; 
        graph = new ArrayList[size];
        long [] b = new long [size];
        for(int i = 0; i < size; i++){
            b[i] = a[i];
        }
        for(int i = 0; i < size; i++){
            graph[i] = new ArrayList<>();
        }
        for(int i = 0; i < edges.length; i++){
            int v1 = edges[i][0];
            int v2 = edges[i][1];
            graph[v1].add(v2);
            graph[v2].add(v1);
        }
        level = new int [size];
        child = new int [size];
        level[0] = 1;
        dfs(0);
        
        // 위상정렬 사용한 풀이 
        while(!list.isEmpty()){
            int cur = list.poll();
            for(int next : graph[cur]){
                if(level[cur] < level[next]) continue;
                answer += b[cur] >= 0 ? b[cur] : -b[cur];
                b[next] += b[cur];
                b[cur] = 0;
                child[next]--;
                if(child[next] == 0){ // 계산할 자식이 더이상 없다면 
                    list.add(next);
                }
            }
        }
        if(b[0] == 0) return answer;
        return -1;
    }
    public static void dfs(int cur){
        for(int next : graph[cur]){
            if(level[next] == 0){
                level[next] = level[cur] + 1;
                child[cur]++;
                dfs(next);
            }
        }
        if(graph[cur].size() == 1){
            int next = graph[cur].get(0);
            if(level[next] < level[cur]){
                list.add(cur); // 리프 노드 추가 
            }
        }
    }
}