[프로그래머스(Programmers)][자바(java)] (Lv3) 모두 0으로 만들기 <월간 코드 챌린지 시즌2>

 

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

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

 

문제 풀이

 

import java.util.*;

public class Solution {

	public static long solution(int[] a, int[][] edges) {
		int n = a.length, wz = 0, i;  long w, s = 0;  // num, cnt with zero weight, weight, sum
		for( i = 0; i < n; ++i ) {
			w = a[i];
			s += w;
			if( w == 0 )
				wz++;
		}
		if( s != 0 )
			return -1;
		if( wz == n )
			return 0;
		int m = n-1, u, v;
		List<List<Integer>> e = new ArrayList<>();
		for( i = 0; i < n; ++i ) 
			e.add( new ArrayList<>() );
		for( i = 0; i < m; ++i ) {
			u = edges[i][0];
			v = edges[i][1];
			e.get(v).add(u);
			e.get(u).add(v);
		}
		long aa[] = new long[n], ans = 0, w;
		for( i = 0; i < n; i++ )
			aa[i] = (long)a[i];
		Queue<Integer> q = new ArrayDeque<>();
		int c[] = new int[n];  // the num of nodes connected of each node
		for( i = 0; i < n; i++ ) {
			c[i] =  e.get(i).size();
			if( c[i] == 1 )  // 연결된 노드가 부모 노드 1개 뿐인 노드 = 자식이 없는 노드 = 리프 노드
				q.add( i );
		}
		boolean b[] = new boolean[n];
		while( !q.isEmpty() ) {
			u = q.remove();
			w = aa[u];
			b[u] = true;
			for( int vv : e.get(u) ) {
				if( b[vv] ) continue;
				aa[u] -= w;
				aa[vv] += w;
				ans += Math.abs( w );
				c[vv]--;
				if( c[vv] == 1 ) 
					q.add( vv );
			}
		}
		return ans;
	}
}

 

-  트리 구조이므로 모든 점들은 서로 연결되어 있으며, 사이클이 존재하지 않음

-  모든 점들의 가중치의 합을 구함
   0이 아니면 트리의 모든 점들의 가중치를 0으로 만드는 것이 불가능하므로 -1 리턴

-  모든 점들의 가중치가 모두 0이면 이미 완성이므로 0 리턴

-  점들의 개수가 최대 300000이고, 인접 행렬을 만들기에는 크기가 크므로 ( 300000 * 300000 ) 인접 리스트를 만듦

-  int a[]에서 점의 가중치를 더하고 빼는 과정에서 값의 오버플로우가 발생할 수 있으므로 long aa[]를 만들어서 long값으로 복사

-  각 점과 연결된 점들의 개수를 담을 int c[] 배열 생성

-  각 점을 방문했는지( 가중치를 0으로 만들었는지 ) 체크하는 boolean b[] 배열 생성

-  연결된 노드( v )가 부모 노드 하나 뿐인, 즉 자식 노드가 없는 리프 노드( = 터미널 노드 )( u )들부터 먼저 BFS 함( 큐 이용 )
   현재 노드( u )의 가중치( aa[u] ) w를 w 만큼 빼줌으로써 0으로 만들고,
   연결된 노드( v )의 가중치( aa[v] )를 w 만큼 더함.
   또한 연산 횟수( ans )를 abs,( w ) 만큼 더함.
   연결된 노드( v )와 인접한 노드가 u를 제외하고 1개면 큐에 담음
 ( 여기서 직접 연결리스트에 접근하여 간선을 삭제한다던가, size()로 연결된 노드들의 개수를 구하는 등의 연산을 하면 시간 초과가 되므로 c[]와 b[] 배열 이용 )