[ 알고리즘 ] 코딩 - Programmers - 모두 0으로 만들기.java

---

문제 링크

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

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

---

문제 개요

프로그래머스 - Level 3 - DFS / 그래프 탐색

각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 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가 나타내는 그래프는 항상 트리로 주어집니다.

 

---

로직

모든 정점의 가중치의 합이 0이 아니라면 모든 정점을 0으로 만드는 것은 불가능 하므로 -1을 리턴한다.

가중치의 합은 int형의 크기보다 커질 수 있으므로 long형 배열로 옮겨 담아준다.

정점의 개수가 30만개로 상당히 많기때문에 리스트로 옮겨준다.

1차원 리스트배열에 정점마다 이어진 정점이 있으면 연결해준다. 

위 정보를 기반으로 DFS를 수행한다. 방문표시를 적절히 해주며 방문을 한 정점은 넘어간다. 

시작 정점에 모든 정점의 가중치의 합이 모이게 된다. 이 모이는 과정에서 + 와 - 가 규칙에 따라 옮겨진다고 생각하고 ANSWER에 현재 정점의 가중치만큼 더해준다.

이 방법이 가능한 이유는 리프 노드는 언젠가는 해당 노드의 가중치만큼의 횟수의 연산을 적용시켜서 가중치를 0으로 만들어야하고, 덧셈의 교환법칙에 의해서 연산을 적용하는 순서가 의미가 없기 때문이라고 한다.

리프 노드부터 해결해 나가면 최소 연산 횟수를 확정적으로 찾을 수 있다.

---

출처 - prgms.tistory.com/47?category=882795

[월간 코드 챌린지 시즌2] 4월 문제 해설

 

---

 

DFS를 수행할 때, 모든 정보를 arguments로 넘겨서 데리고 다녔는데 그렇게 하면 테스트 7, 8번에서 런타임 에러를 만나게 된다. 다음 정점을 가리키는 vertex를 제외하고 모든 변수를 static으로 바꿔주면 실행시간을 가득채워서 성공한다. 이유는... 잘모르겠다.. 질문하기란에 보니 서버와 테스트케이스 문제라는 이야기가 있지만, 정확하지는 않은 것 같다.

 

---

코드

import java.util.ArrayList;
import java.util.List;

class Solution { // static 필수
		static long ANSWER, ln_a[];
		static boolean[] visited;
		static List<Integer>[] edge_list;
	    public long solution(int[] a, int[][] edges) {
	    	int length = a.length;
	    	ln_a = new long[length];
	    	edge_list = new ArrayList[length];
	    	long sum = 0;
	    	
	    	for(int i = 0; i < length; i++) {
	    		edge_list[i] = new ArrayList<Integer>();
	    		sum += ln_a[i] = a[i];
	    	}
	    	
	    	if(sum != 0) return -1;
	    	
	    	for(int i = 0; i < edges.length; i++) {
	    		edge_list[edges[i][0]].add(edges[i][1]);
	    		edge_list[edges[i][1]].add(edges[i][0]);
	    	}
	    	
	    	visited = new boolean[length];
	    	visited[0] = true;
	    	dfs(0);
	    	
	        return ANSWER;
	    }
		
	    
		private long dfs(int vertex) { // 모든 정점 탐색
			for(int i = 0; i < edge_list[vertex].size(); i++) {
				int next_vertex = edge_list[vertex].get(i);
				if(visited[next_vertex]) continue;
				visited[next_vertex] = true;
				ln_a[vertex] += dfs(next_vertex); // 한 곳으로 모아주자
			}
			ANSWER += Math.abs(ln_a[vertex]); // 현재 가중치를 더해줌
			return ln_a[vertex];
		}
	}