[프로그래머스,자바] Level3: 모두 0으로 만들기

 

 

문제분석

 

목표:  모든 노드의 값(가중치)을  0으로 만든뒤  최소 연산의 횟수를 구해주세요.

 

특징1. 인접한 노드끼리는 값을 주고받을수있다.

 

 

 

모든 값을 0으로 만들기위해선  노드와 노드끼리 값을 교환할수밖에 없기때문에,

 

그래프를 그릴필요가있다.

 

그래프를 그리는법은 여러방법이있다.

 

Graph 리스트를 하나 만들어 저장하거나,  객체를 만들어서 저장하거나..

 

필자는 객체 Node를 만들어서 그래프를 그려보려고한다.

 

 

전략은 각 노드마다 child 리스트를 생성한다.  그 노드가 갖고있는 자식노드를 통해 연결고리를 만드는것이다.

 

 

 

문제에서 데이터를 주고받는건 양방향이니 (자식 ->부모 , 부모 ->자식)  양방향으로 잡아주자.

 

사실  부모 -> 자식으로 데이터가 들어오는게 100%확정이라면 양방향으로 안해도 되지만, 

그렇게 들어온다는 보장이 없으니 양방향으로 잡아주자..

 

단,  이렇게 양방향으로 만들어놓으면  무한루프에 위험이 있기때문에 방문체크를 해줘야한다.

 

 

 

탐색 방법은 DFS() 사용하였다.   우리가 원하는건 연산 횟수니, 

 

자식의 가중치 값 =  연산횟수 라고 생각하면 된다. 어처피 모두 0으로 만들어야하기 때문이다.

 

문제풀이

import java.util.*;
class Node {    
    public long value;
    public int idx;
    public List<Node> child = new ArrayList<>();
    
    public Node (int idx,long value){
        this.idx=idx;
        this.value=value;
    }
    
}
 
class Solution {
    
long result=0;
boolean[] visited;
Node[] arr ;
    
    public long solution(int[] a, int[][] edges) {
        long answer = -2;
        
        long[] a1 = new long[a.length];
        
        for(int i=0;i<a.length;i++){
            a1[i]=a[i];
        }
        
        
        arr = new Node[a.length];
        visited = new boolean[a.length];
        
        int total=0;
        
        for(int i=0;i<a.length;i++){
            arr[i] = new Node(i,a1[i]);    
            total+=a1[i];
        }
        
        if(total!=0){
            return -1;
        }
        
        for(int i=0;i<edges.length;i++){
            arr[edges[i][0]].child.add(arr[edges[i][1]]);
            arr[edges[i][1]].child.add(arr[edges[i][0]]);
        }
        
        search(arr[0]);
        
        return result;
    }
    
    public long search(Node root){
        int size=root.child.size();
        
        visited[root.idx]=true;
        
         for(int i=0;i<size;i++){
            if(visited[root.child.get(i).idx]==true){       
               continue;
            }  
             root.value+= search(root.child.get(i));
         }
    
        result+=(long)Math.abs(root.value);
        return root.value;
    }
}