[프로그래머스]모두 0으로 만들기 - JAVA

[프로그래머스]모두 0으로 만들기 - JAVA

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

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

풀이

많이 해메였던 문제이다. 모든 정점의 가중치를 0으로 만들려면 필요한 아이디어를 먼저 살펴보자.

 

1. 모든 가중치의 합이 0이된다. (0이 되지 않으면 애초에 모든 정점의 가중치를 0으로 만들 수 없다)
2. 한 방향으로 탐색을 진행하면서 가중치 연산을 해야 한다. (목적 노드를 하나 정해두고 나머지 리프 노드에서부터 목적 노드까지 가중치를 계산하며 연산 횟수를 누적시켜 한번의 탐색으로 원하는 결과를 얻을 수 있다)

 

한 방향으로 탐색을 할때 목적 노드는 어떤 노드로 할 것이며 리프 노드는 어떻게 찾을 것인지 고민해 보았다. 리프노드를 찾아주고 순차적으로 탐색을 할 수 있도록 "위상정렬" 알고리즘을 활용하였다.

 

• 모든 노드의 간선의 수를 저장한다. (이때 간선은 방향이 없는 무향 그래프) 
• 간선의 수가 1개(진출만 존재)인 경우 리프노드로 간주하고 탐색 큐에 넣어준다.
• 현재 노드와 연결된 노드로 이동하며 방문했으므로 연결 노드의 간선의 수를 줄여준다.
• 현재 노드에서 연결된 노드로 가중치를 옮겨준다. (이때 가중치의 합은 int범위를 넘을 수 있으므로 long배열을 따로 생성해 준다.) 이 과정은 인접 노드끼리 +1, -1연산을 해 준것과 같은 의미이다.
• 현재 노드에서 연결된 노드로 이동시킨 가중치 만큼 result에 더해준다. 
• 현재 노드는 모든 가중치 값을 연결 노드로 이동시켰으므로 가중치 값을 0으로 변경해준다.
• 연결 노드의 간선의 수가 1이라면 리프노드가 된 것이므로 탐색 큐에 담아준다.

위 연산의 일련 과정을 예제 경우일때 그림으로 표현하면 다음과 같다.

 

코드

import java.util.*;
 
class Solution {
    
    ArrayList<Integer>[] list; //간선 정보로 list생성
    boolean[] visited;
    int[] indegree; //진입 간선
    long[] long_a; //연산 수행 위한 long배열
    long result; 
    
    public long solution(int[] a, int[][] edges) {
        long_a = new long[a.length];
        list = new ArrayList[a.length];
        long sum = 0; 
        for(int i = 0; i < a.length; i++) {
            sum += a[i];
            long_a[i] = a[i];
            list[i] = new ArrayList<>();
        }
        if(sum != 0) return -1;
        
        indegree = new int[a.length];
        for(int i = 0; i < edges.length; i++) {
            list[edges[i][0]].add(edges[i][1]);
            list[edges[i][1]].add(edges[i][0]);
            indegree[edges[i][0]]++;
            indegree[edges[i][1]]++;
        }
        
        visited = new boolean[a.length];
        topology(); //위상정렬 알고리즘 활용하여 리프노드에서 루트까지 가중치 이동횟수 구함
        return result;
    }
    
    public void topology() {
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < indegree.length; i++) {
            if(indegree[i] == 1) q.offer(i);
        } 
        
        while(!q.isEmpty()) {
            int current = q.poll();
            visited[current] = true;
            
            for(int i = 0; i < list[current].size(); i++) {
                int next = list[current].get(i);
                if(!visited[next]) {
                    indegree[next]--;
                    long_a[next] += long_a[current];// +1, -1해주었다고 생각하여 합친 값을 저장    
                    result += Math.abs(long_a[current]); // 현재 노드에서 이동한 값 만큼 result에 더해줌 
                    long_a[current] = 0; // 현재 노드의 모든 가중치 값을 부모로 이동.
                    if(indegree[next] == 1) q.offer(next); 
                }
            }
        }
    }
}