알고리즘/프로그래머스(Programmers)
[프로그래머스][월간 코드 챌린지 시즌2][자바] 모두 0으로 만들기
NineOne
2021. 4. 15. 22:31
programmers.co.kr/learn/courses/30/lessons/76503
코딩테스트 연습 - 모두 0으로 만들기
각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다. 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한
programmers.co.kr
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