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

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

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

import java.io.*;
import java.util.*;

class Solution {
    public long solution(int[] a, int[][] edges) {
        long answer = 0;
        long[] temp = new long[a.length];
        
        if(Arrays.stream(a).sum() !=0) return -1;
        
        //노드가 2개 인데 서로 이어져 있을때
        if(a.length == 2) {
        	a[0] += a[1];
        	if(a[0] !=0 ) return -1;
        	else return Math.abs(a[1]);
        }
        
        //타입을 long으로 바꿔줌
        for(int i=0; i<a.length; i++) {
        	temp[i] = a[i];
        }
        
        long distance[] = new long[a.length];
        boolean[] visited = new boolean[a.length];
        List<Integer>[] list = new List[a.length];
        
        for(int i=0; i<a.length; i++) {
        	list[i] = new ArrayList<>();
        }
	
    	//간선 정보 및 노드 진입 차수 정보 입력
        for(int i=0; i<edges.length; i++) {
        	list[edges[i][0]].add(edges[i][1]);
        	list[edges[i][1]].add(edges[i][0]);
        	distance[edges[i][1]]++;
        	distance[edges[i][0]]++;
        }
        
        Queue<Integer> qu = new LinkedList<>();
        //진입 노드 1인거 집어 넣기 -> 리프 노드에 해당
        for(int i=0; i<distance.length; i++) {
        	if(distance[i] ==1) {
        		qu.offer(i);
        		visited[i] = true;
        	}
        }
        
        while(!qu.isEmpty()) {
        	int no = qu.poll();     
        	visited[no] = true;
        	
        	for(int i=0; i<list[no].size(); i++) {
        		int curr = list[no].get(i);
        		if(visited[curr]) continue;
        		distance[curr]--;
        		temp[curr] += temp[no];
        		answer += Math.abs(temp[no]);
        		temp[no] =0;
        		
        		if(distance[curr] ==1) {
        			qu.offer(curr);
        		}
        	}
        }
        
        for(int i=0; i<a.length; i++) {
        	if(temp[i] != 0) {
        		answer =-1;
        		break;
        	}
        }
        
        return answer;
    }
    
}

정리

• 위상정렬을 응용해서 풀었습니다.
• 방향 그래프가 아니기 때문에 진입 노드의 수가 1인 것들을 먼저 집어 넣어 주었습니다. 진입 노드가 1이라면 리프노드에 해당되기 때문입니다.
• Queue를 이용해 진입 노드1인 것들을 꺼내면서 간선들을 제거해주었습니다.
• 간선을 없애주는 과정에서 자신의 절대 값을 계속 더해주면 됩니다. ( 합쳐지는 과정 )
• 이후 진입 노드가 1이 되면 Queue에 넣어주고 반복하면 됩니다.
• temp배열에 값이 남아 있다면 제대로 합쳐지지 않았기에 false