자바(JAVA) - 모두 0으로 만들기(Programmers : 76503)

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

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

 

생각했던것보다 아주 많이,, 오래 걸린 문제.

가중치를 어떻게 올바르게 카운트 할 수 있을지 너무 어렵게 생각했던 것 같다..
반환값이 long인 부분을 고려하여 입력값을 long 타입으로 옮겨주는 작업,
그리고 아직도 왜 그런지 모르겠지만 변수화 여부에 따라 결과값이 다르게 나오던 문제를 해결하고나서야 겨우 All Pass를 받을 수 있었다..

 

실행 순서는 다음과 같다 :

    1. int[] a > long 타입 배열에 입력

    2. 모든 weight를 더하여 0이 아닌 경우 -1 반환

    3. 간선 정보 ArrayList 배열에 입력

    4. DFS를 통해 각 가중치 업데이트하며 + 업데이트된 가중치 Count

 

<코드>

import java.util.*;

class Solution {
	long answer = 0;
	ArrayList<Integer>[] adjList;
	int len;
	boolean[] visited;
	long[] longAns;

	public long solution(int[] a, int[][] edges) {
		this.len = a.length;
		this.adjList = new ArrayList[this.len];
		this.visited = new boolean[this.len];
		this.longAns = new long[this.len];

		long s = 0;

		for (int i = 0; i < this.len; i++) {
			this.longAns[i] = a[i];
			s += a[i];
			this.adjList[i] = new ArrayList<Integer>();
		}

		// input 유효성 확인 - 전체 합이 0이 아닐 경우 불가능
		if (s != 0) {
			return -1;
		}

		// 간선 정보 adjList 에 입력
		for (int[] edge : edges) {
			int node1 = edge[0];
			int node2 = edge[1];
			this.adjList[node1].add(node2);
			this.adjList[node2].add(node1);
		}

		dfs(0);

		return answer;
	}

	public long dfs(int index) {
		this.visited[index] = true;

		// 간선 노드를 확인하며 가중치 업데이트
		for (int i = 0; i < this.adjList[index].size(); i++) {
			int curr = this.adjList[index].get(i);
			if (visited[curr] == false) {
				this.longAns[index] += dfs(curr);
			}
		}
		this.answer += Math.abs(longAns[index]);
		return longAns[index];
	}
}