[ 프로그래머스 / Programmers Level 3 ] 모두 0으로 만들기 ( JAVA / 자바 )

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

코딩테스트 연습 - 모두 0으로 만들기

 

문제

---

각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다.

• 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한쪽은 1 감소시킵니다.

하지만, 모든 트리가 위의 행동을 통하여 모든 점들의 가중치를 0으로 만들 수 있는 것은 아닙니다. 당신은 주어진 트리에 대해서 해당 사항이 가능한지 판별하고, 만약 가능하다면 최소한의 행동을 통하여 모든 점들의 가중치를 0으로 만들고자 합니다.

트리의 각 점의 가중치를 의미하는 1차원 정수 배열 a와 트리의 간선 정보를 의미하는 edges가 매개변수로 주어집니다. 주어진 행동을 통해 트리의 모든 점들의 가중치를 0으로 만드는 것이 불가능하다면 -1을, 가능하다면 최소 몇 번만에 가능한지를 찾아 return 하도록 solution 함수를 완성해주세요. (만약 처음부터 트리의 모든 정점의 가중치가 0이라면, 0을 return 해야 합니다.)

제한 사항

---

• a의 길이는 2 이상 300,000 이하입니다.
  • a의 모든 수는 각각 -1,000,000 이상 1,000,000 이하입니다.
  • a[i]는 i번 정점의 가중치를 의미합니다.
• edges의 행의 개수는 (a의 길이 - 1)입니다.
  • edges의 각 행은 [u, v] 2개의 정수로 이루어져 있으며, 이는 u번 정점과 v번 정점이 간선으로 연결되어 있음을 의미합니다.
  • edges가 나타내는 그래프는 항상 트리로 주어집니다. 

예제

---

입출력 예

a	edges	result
[-5,0,2,1,2]	[[0,1],[3,4],[2,3],[0,3]]	9
[0,1,0]	[[0,1],[1,2]]	-1

입출력 예 #1

• 다음 그림은 주어진 트리의 모든 정점의 가중치를 0으로 만드는 과정을 나타낸 것입니다.

1. 2번 정점과 3번 정점을 선택하여 2번 정점은 1 감소시키고, 3번 정점은 1 증가시킵니다. (2번 반복)
2. 3번 정점과 4번 정점을 선택하여 4번 정점은 1 감소시키고, 3번 정점은 1 증가시킵니다. (2번 반복)
3. 0번 정점과 3번 정점을 선택하여 3번 정점은 1 감소시키고, 0번 정점은 1 증가시킵니다. (5번 반복)

• 모든 정점의 가중치를 0으로 만드는 데 필요한 최소 행동 횟수는 9번이므로, 9를 return 해야 합니다.

입출력 예 #2

• 주어진 트리는 모든 정점의 가중치를 0으로 만드는 것이 불가능하므로, -1을 return 해야 합니다.

 

풀이

---

모든 노드의 가중치의 합이 0이 되지 않으면 👉 모든 노드를 0으로 만들 수 ❌ return -1

모든 노드의 가중치의 합이 0이면 👉  연결된 노드가 1개인 노드부터 0으로 만들기 시작 ‼️

1️⃣ 큐에 연결된 노드가 1개인 노드 즉, leaf node 들을 저장

2️⃣ 큐에 저장된 노드now의 가중치를 0으로

    ➡️ 연결된 노드next에 now의 가중치만큼 ✚

    ➡️ next의 indegree −

3️⃣ next의 indegree가 1 이면 큐에 추가

 코드

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class 모두0으로만들기 {
    
    static ArrayList<Integer> adj[];
    static boolean[] isVisited;
    static int[] indegree;
    static long[] longA;
    static long answer;
    public static long solution(int[] a, int[][] edges) {
        answer = 0;

        longA = new long[a.length];
        adj = new ArrayList[a.length];
        indegree = new int[a.length];
        isVisited = new boolean[a.length];

        long sum = 0;
        for(int i = 0 ; i < a.length ; i++){
            sum += a[i];
            longA[i] = a[i];
            adj[i] = new ArrayList<>();
        }

        if(sum != 0)
            return -1;

        for(int i = 0 ; i < edges.length ; i++){
            adj[edges[i][0]].add(edges[i][1]);
            adj[edges[i][1]].add(edges[i][0]);
            
            indegree[edges[i][0]]++;
            indegree[edges[i][1]]++;
        }
        
        BFS();

        return answer;
    }

    private static void BFS() {
        Queue<Integer> queue = new LinkedList<>();

        for(int i = 0 ; i < indegree.length ; i++){
            if(indegree[i] == 1)
                queue.offer(i);
        }

        while(!queue.isEmpty()){
            int now = queue.poll();
            isVisited[now] = true;

            for(int next : adj[now]){
                if(!isVisited[next]){
                    indegree[next]--;
                    longA[next] += longA[now];
                    answer += Math.abs(longA[now]);
                    longA[now] = 0;

                    if(indegree[next] == 1)
                        queue.offer(next);
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {-5, 0, 2, 1, 2};
        int[][] edges = {{0, 1}, {3, 4}, {2, 3}, {0,3}};

        System.out.println(solution(a, edges));
    }
}

 

---