[Algorithm] 프로그래머스 - 모두 0으로 만들기 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

이번 문제는 프로그래머스 모두 0으로 만들기 자바 풀이를 작성하도록 하겠습니다.

 

문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/76503#

프로그래머스

 

 

1. 풀이 소스

 

import java.util.*;

class Solution {
    public long solution(int[] a, int[][] edges) {
        Graph graph = new Graph(a);
        
        if (graph.isInitEnd() == 0 || graph.isInitEnd() == -1) {
            return graph.isInitEnd(); // 0 또는 -1 종료 조건
        }
        
        graph.addEdge(edges); // graph에 edge 설정
        graph.dfs(0);      
        
        return graph.getAnswer();
    }
}

class Graph {
    
    Node[] nodes; // 노드 배열
    boolean[] visited; // 방문 여부
    long answer; // 정답 long 타입!
    boolean isAllZero; // 모두 0인지 아니면 어떤 수는 0이 아닌지로 종료 여부 체크
    long isPossibleSumZero; // 합이 0이 가능한지 체크
    
    class Node {
        int x;
        long w;
        List<Node> adjacent = new ArrayList<>();
        
        Node (int x, long w) {
            this.x = x;
            this.w = w;
        }
    }
    
    Graph(int[] arr) {
        nodes = new Node[arr.length]; // 노드 배열
        visited = new boolean[arr.length]; // 방문 여부 체크
         
        for (int i = 0; i < nodes.length; i++) {
            nodes[i] = new Node(i, arr[i]); // 노드 생성
            if (arr[i] != 0) this.isAllZero = false; // 하나라도 0이 아니라면 어떤 수는 0이 아니므로 false
            isPossibleSumZero += arr[i]; // 모든 수의 합이 zero가 될 수 있는지 체크
        }
        
    } 
    
    
    int isInitEnd() {
        if (isPossibleSumZero != 0) return -1; // 모든 수의 합이 0이 안된다면 조료
        if (this.isAllZero) return 0; // 이미 모든 수가 0이라면 종료
        return 1; 
    }
    
    void addEdge(int[][] edges) {
        
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0]; // edge 설정
            int v = edges[i][1];
            
            Node n1 = nodes[u];
            Node n2 = nodes[v];
            
            n1.adjacent.add(n2); // 양방향 연결관계
            n2.adjacent.add(n1);
        }
    }
    
    long dfs(int x) {
        
        visited[x] = true; // 방문 체크
        
        Node node = nodes[x]; // 노드 설정
        
        for (int i = 0; i < node.adjacent.size(); i++) {
            Node adjacent = node.adjacent.get(i); // 인접한 노드 가져옴
            
            if (!visited[adjacent.x]) {
                node.w += dfs(adjacent.x); // dfs로 인접한 노드로부터 가중치를 업데이트하여 가져옴 --> 중간 노드가 선택된다면 리프노드로 계속 방문하여 w 업데이트 
            }
        }
        
        this.answer += Math.abs(node.w); // 노드의 가중치의 절대값을 더함 (- 혹은 + 도 0으로 만들기 위해서는 정량적인 수가 필요하므로)
        
        return node.w; // 노드의 가중치를 리턴하여 dfs
    }
    
    
    long getAnswer() {
        return this.answer;
    }
    
}

 

 

2. 풀이 과정

 

해당 문제는 연결된 트리가 zeroSum을 통해 0이 될 수 있는지 판별할 수 있는 조건이 필요했습니다.

이를 위해 모든 수의 합이 0이 된다면, 연결위치에 상관없이 모두 0으로 만들 수 있다는 사실에 근거하여,

먼저 isPossibleSumZero가 가능한지 판별하였습니다.

또한 모두 0인지 판단하기 위한 조건을 isAllZero를 추가하여 조기 종료가 수행될 수 있도록 하였습니다.

 

핵심 로직은 dfs를 이용하여 풀이를 했습니다. 

 

          1 -- 1 -- 1 -- 1
          |
 -9  -- 1 -- 2 
  |     |   

  0     2

 

이와 같은 트리 구조가 있다고 가정하겠습니다.

dfs로 0번째 인덱스를 선택했을 때, 0이 선택된다면 인접한 노드를 검색합니다. 

 

인접한 노드 1(가중치 -9)를 선택하게 되면서 노드 1에 대한 dfs를  진행합니다. 

즉, 노드 1의 인접한 노드인 노드 2(가중치 1)를 찾은 후 다시 dfs를 적용하는 방식으로 재귀적 호출로 최종 리프(루트) 노드에 도달하게 된다면, 더 이상 방문할 노드가 없으므로 answer를 업데이트하고 node.w를 리턴하며 재귀적으로 node.w가 업데이트하게 됩니다,

 

최종적으로 answer를 리턴하면 됩니다.

해당 문제에 대한 테스트 케이스를 추가로 작성하였는데 공유드리겠습니다.

 

//        1 -- 1 
//        |
// -7  -- 1 -- 2
//  |     |
//  0     2
//  

// 7 + 2 + 4  = 14


//        1 -- 1 -- 1 -- 1
//        |
// -9  -- 1 -- 2 
//  |     |    
//  0     2


//  9 + 2 + 2 + 1 + 2 + 3 + 4  = 23


//                              -2
//                             /
//   2 -- 2 -- 2       -8 -- -7 -- -2 
//              \     /  \
//    3 -- 2 -- 8 -- 7    -2 -- -3
//                          \
//                           -2
// 92

 

테스트 케이스 

[-7, 0, 2, 1, 2, 1, 1], [[0, 1], [3, 4], [2, 3], [0, 3], [5, 3], [6, 5]], 14

 

[-9, 0, 2, 1, 2, 1, 1, 1, 1], [[0, 1], [3, 4], [2, 3], [0, 3], [5, 3], [6, 5], [7, 6], [8, 7]], 23

 

[-9, 0, 2, 1, 2, 1, 1, 1, 1, -18, 18]. [[0, 1], [3, 4], [2, 3], [0, 3], [5, 3], [6, 5], [7, 6], [8, 7], [9, 0], [10, 2]], 95

 

[2, 2, 2, 3, 2, 8, 7, -8, -7, -2, -2, -2, -3, -2], [[0, 1], [1, 2], [3, 4], [4, 5], [2, 5], [5, 6], [6, 7], [7, 8], [8, 9], [8, 10], [7, 11], [11, 12], [11, 13]], 92

 

이상으로 해당 문제 풀이를 마치겠습니다.! 감사합니다.