모두 0으로 만들기 :
그림을 그려서 조금 끄적거리다보면서 모든 정점의 가중치를 0으로 만들수 있는 방법이 보입니다.
이 4가지를 발견하고 들어가서 문제를 좀더 쉽게 접근할 수 있었습니다.
먼저 각 트리의 정점의 인접리스트를 생성합니다.
그 후, 0번째 정점부터 시작하여 DFS를 시작해줍니다.
인접한 정점으로 이동하면서 인접 정점이 0이 되도록 DFS에서 반환되는 인접 정점의 가중치를 현재 정점의 가중치에 더해줍니다.
이때, 더 이상 탐색할 인접 정점이 없는 트리는 자신의 가중치를 반환해줍니다.
a = [-5,0,2,1,2] / edges = [[0,1],[3,4],[2,3],[0,3]] 으로 예시를 들어보겠습니다.
DFS를 시작할때 0 정점
으로 시작하겠습니다.
0 정점
에서 인접 정점 1 정점
을 탐색한다면 1 정점
은 더이상 인접한 정점이 없기 때문에 자신을 반환하게 되고, 0 정점
은 자신의 가중치에 1 정점
의 가중치 0을 더해줍니다.
그리고 다음 인접 정점인 3 정점
으로 이동합니다.
3 정점
에서의 인접 정점인 2 정점
에 접근합니다. 2 정점
은 더 이상 인접한 정점이 없기 때문에 자신의 가중치를 반환하게 되고 3 정점
은 2 정점
의 가중치(2)를 더해줍니다.
(현재 3 정점
의 가중치 3)
그 다음 3 정점
의 인접 정점인 4 정점
에 접근합니다. 3 정점
도 더 이상 인접한 정점이 없기 때문에 자신의 가중치를 반환하게 되고, 3 정점
은 4 정점
의 가중치(2)를 더해줍니다.
(현재 3 정점
의 가중치 5)
그 후, 더 이상 인접 정점이 없는 3 정점
은 현재 자신의 가중치인 5를 반환합니다.
다시 0 정점
으로 돌아와서 3 정점
의 가중치인 5를 반환받게 되고 0 정점
은 자신의 가중치에 5를 더해줍니다.
그렇다면 0 정점
의 가중치는 0이 되므로 해당 트리의 모든 정점은 0이 되게 됩니다.
이 때, 주의할 점이 있습니다.
a의 모든 수가 최소 -1000000, 최대 1000000이고 a의 최대 길이가 300000이기 때문에 가중치가 int크기를 넘어갈 수 있기 때문에 long타입
을 사용해주어야 합니다.
class Solution {
long answer;
long sum;
int N;
long[] longA;
List<Integer>[] edge;
boolean[] check;
public long solution(int[] a, int[][] edges) {
N = a.length;
initEdge(a, edges);
//모든 가중치의 합이 0이 되지 않는다면 모든 정점은 0으로 만들 수 없습니다.
if(sum != 0) return -1;
answer = 0;
dfs(a, 0);
return answer;
}
//dfs로 트리 끝까지 이동하고 자식 노드의 값을 자신의 노드값을 더해서 부모 노드에게 반환
public long dfs(int[] a,int idx){
long num = a[idx];
check[idx] = true;
for(int i=0;i<edge[idx].size();i++){
int next = edge[idx].get(i);
if(check[next]) continue;
num += dfs(a, next);
}
//for-each를 이용한 반복 (런타임)
// for(int e : edge[idx]){
// if(check[e]) continue;
// num += dfs(a, e);
// }
answer += Math.abs(num);
return num;
}
//인접리스트 만들기
public void initEdge(int[] a, int[][] edges){
edge = new List[N];
check = new boolean[N];
sum = 0;
for(int i=0;i<N;i++){
edge[i] = new ArrayList<>();
sum += a[i];
}
for(int[] e : edges){
int u = e[0];
int v = e[1];
edge[u].add(v);
edge[v].add(u);
}
}
}
코드에 for-each문으로 만든 코드가 주석처리 되어있는데.. 다른 테스트케이스도 넣어보고 잘 통과하는데 for-each로 구현을 하면 몇몇 테스트 케이스에서 런타임이 발생합니다.
for-each를 애용하는 편이라 이 부분이 틀릴거라 생각하지 못했는데 for문을 이용해서 사용하니 통과가 되더군요..
이렇게 맞왜틀을 오래 외친 문제는 처음인것 같습니다.. 아직도 왜 for-each문은 런타임이 발생하는지 모르겠습니다..
시간초과면 모를까.. 혹시 의심되는 부분이 있다면 지적해주시면 감사하겠습니다.