[프로그래머스] 모두 0으로 만들기 / Java

문제주소 :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가 나타내는 그래프는 항상 트리로 주어집니다.

---

입출력 예

aedgesresult

[-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 해야 합니다.

 

<풀이법>

▒ 한줄 개념: 그래프 ▒ 

처음에는 bfs를 통해 값이 양수인 모든 vertex에서 값이 음수인 vertex를 찾아가면서 모든 값을 0으로 만들어주는 방법을 생각했다. 하지만 시간도 너무 오래걸리고, 구현적으로 너무 복잡해져서 포기하였다.

 

그 후 다른 방법을 생각하다가, 프로그래머스 공식 문제 해설을 보고 풀이하였다.

prgms.tistory.com/47?category=882795

[월간 코드 챌린지 시즌2] 4월 문제 해설

 

 

간단한 문제 풀이 방식은 다음과 같다.

 

1. a[]의 전체 합산이 0인지 확인한다. 전체 합이 0이 아니면 -1을 리턴한다.

2. edge를 이용해 ArrayList<>[]를 만들어준다. matrix로 하기에는 a의 갯수가 너무 많다.

3. visited[]배열과 dfs를 통해 leaf vertex까지 쭉 들어갔다가 차례차례 올라온다.

4. 부모 vertex는 자식 vertex의 value를 받아 자신의 value에 더하고, 모든 vertex는 자신의 value의 절댓값을 answer에 합산하게 된다.

 

 

<코드(Java)>

import java.util.*;

class Solution {

        long answer;
        boolean[] visited;
        long[] long_a;
        ArrayList<Integer>[] children;

        public long solution(int[] a, int[][] edges) {
            this.answer = 0;
            this.visited = new boolean[a.length];
            this.children = new ArrayList[a.length];
            this.long_a = new long[a.length];

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

            if(sum != 0) return -1;

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

            dfs(0);

            return answer;
        }

        public long dfs(int v){
            this.visited[v] = true;
            
            for(int i = 0; i < children[v].size(); i++){
                int next = children[v].get(i);
                if(!visited[next]){
                    long_a[v] += dfs(next);
                }
            }

            this.answer += Math.abs(long_a[v]);

            return long_a[v];
        }

    }

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest