프로그래머스 - 76503 : 월간 코드 챌린지 시즌2 - 모두 0으로 만들기 (자바 - 위상정렬 , 인접리스트 , 인접 행렬 풀이 및 오류 8번, 11번, 17번 오답노트

프로그래머스 / 월간 코드 챌린지 시즌2 / 모두 0으로 만들기 

 

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

프로그래머스

 

 

문제 설명

각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 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으로 만드는 과정을 나타낸 것입니다.

2번 정점과 3번 정점을 선택하여 2번 정점은 1 감소시키고, 3번 정점은 1 증가시킵니다. (2번 반복)
3번 정점과 4번 정점을 선택하여 4번 정점은 1 감소시키고, 3번 정점은 1 증가시킵니다. (2번 반복)
0번 정점과 3번 정점을 선택하여 3번 정점은 1 감소시키고, 0번 정점은 1 증가시킵니다. (5번 반복)
모든 정점의 가중치를 0으로 만드는 데 필요한 최소 행동 횟수는 9번이므로, 9를 return 해야 합니다.

 

입출력 예 #2

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

 

---

나의 풀이

 

이 문제를 처음 보았을 땐 DFS를 써서 위상정렬로 풀어야한다는 걸 알았다. 하지만 매번 풀이가 직관적으로 보기 쉬운 인접행렬을 썼어서 이 문제 또한 인접행렬로 풀어 버렸다.

 

인접행렬 풀이

 

import java.util.*;
 
public class makeAllZero2_matrix {
    static long answer = 0;
 
    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));
    }
 
    public static long solution(int[] a, int[][] edges) {
        int nodeNum = a.length;
        int[][] graph = new int[nodeNum][nodeNum];
 
        for (int i = 0; i < edges.length; i++) {
            graph[edges[i][0]][edges[i][1]] = 1;
            graph[edges[i][1]][edges[i][0]] = 1;
 
        }
        Stack<Integer> dfs = new Stack<>();
        Stack<Integer> order = new Stack<>();
        Set<Integer> visited = new HashSet<>();
        dfs.push(0);
        visited.add(0);
 
        while (dfs.size() != 0) {
            int nextNode = dfs.pop();
            order.push(nextNode);
            for (int i = 0; i < nodeNum; i++) {
                if (graph[nextNode][i] == 1 && !visited.contains(i)) {
                    dfs.push(i);
                    visited.add(i);
                }
            }
        }
        Set<Integer> visited2 = new HashSet<>();
 
        while (order.size() > 1) {
            int leafNode = order.pop();
            visited2.add(leafNode);
            for (int i = 0; i < nodeNum; i++) {
                if (graph[leafNode][i] == 1 && !visited2.contains(i)) {
                    a[i] += a[leafNode];
                    answer += Math.abs(a[leafNode]);
                }
            }
        }
        if (a[0] + a[order.peek()] == 0) {
            return answer + Math.abs(a[order.peek()]);
        } else {
            return -1;
        }
    }
}

 

제출 결과 메모리 초과가 떴다.

 

하지만 문제에서 원하는 점은 인접 리스트를 풀어서 메모리를 아껴서 푸는 방식을 원한 것이다.

(그리고 가중치를 더해서 저장할 long[] 또한 만들어주지 않아 틀린 답이기도 하다.  long[]을 만들어서 넣어주어 메모리제한이 없는 제출지에 제출한다면 아마 정답처리 될 것이라 생각한다.)

 

 

메모리 초과로 인해 인접리스트로 다시 풀었다.

 

인접리스트 풀이

public class makeAllZero2_list_answer2 {
    static long answer = 0;
 
    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));
    }
 
    public static long solution(int[] a, int[][] edges) {
        int nodeNum = a.length;
        long[] answerArr = new long[nodeNum + 1];
        for (int i = 0; i < nodeNum; i++) {
            answerArr[i] = a[i];
        }
        List<List<Integer>> connection = new ArrayList<>();
 
        for (int i = 0; i <= nodeNum; i++) {
            connection.add(new ArrayList<>());
        }
 
        for (int i = 0; i < nodeNum - 1; i++) {
            connection.get(edges[i][0]).add(edges[i][1]);
            connection.get(edges[i][1]).add(edges[i][0]);
        }
        Stack<Integer> dfs = new Stack<>();
        Stack<Integer> order = new Stack<>();
        Set<Integer> visited = new HashSet<>();
        dfs.push(0);
        visited.add(0);
 
        while (dfs.size() != 0) {
            int nextNode = dfs.pop();
            order.push(nextNode);
            for (int i = 0; i < connection.get(nextNode).size(); i++) {
                if (!visited.contains(connection.get(nextNode).get(i))) {
                    dfs.push(connection.get(nextNode).get(i));
                    visited.add(connection.get(nextNode).get(i));
                }
            }
        }
        Set<Integer> visited2 = new HashSet<>();
 
        while (order.size() > 1) {
            int leafNode = order.pop();
            visited2.add(leafNode);
            for (int i = 0; i < connection.get(leafNode).size(); i++) {
                if (!visited2.contains(connection.get(leafNode).get(i))) {
                    answerArr[connection.get(leafNode).get(i)] += answerArr[leafNode];
                    answer += Math.abs(answerArr[leafNode]);
                }
            }
        }
        if (answerArr[0] + answerArr[order.peek()] == 0) {
            return answer + Math.abs(answerArr[order.peek()]);
        }
        return -1;
    }
}

 

 

인접행렬은 직관적으로 노드와 노드가 연결된 모습을 확인할 수 있어 좋지만, 이중 배열을 사용하기때문에 노드의 수가 많아지면 메모리 초과가 뜨기 쉽상이다. 따라서

인접 리스트 풀이 법이 더 안전하게 풀 수 있다.