프로그래머스 - 모두 0으로 만들기 (자바)

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

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

이문제는 위상정렬을 이용해서 풀수 있습니다.

우선 모든 가중치의 합이 0이 안되면 불가능함으로 -1을 리턴

 

edges를 순회하면 graph에 양방향으로 간선을 연결해주고

간선에 연결된 두개의 노드를 +1해주면서 각 노드의 진입차수를 셋팅합니다.

 

큐를 만들어서 진입차수가 1인 노드들을 넣어줍니다. 

진입차수가 1이라는 의미는 연결된 노드가 하나라는 의미로 모든 가중치가 0이 될려면

진입차수가 1인 노드의 가중치가 연결된 단 하나의 노드로 보내져야 합니다.

 

이후 큐를 순회하면서

방문처리를 하고

연결된 노드의 방문하지 않은 경우

연결되 노드의 진입차수를 -1하고

연결된 노드에게 가중치 전부를 넘기고

넘긴 가중치의 절대값만큼 answer를 올려줍니다. 

그리고 만약 연결된 노드의 진입차수가 1이라면 큐에 추가해줍니다.

 

이후 모든 노드의 가중치가 0 이라면 계산한 answer를 리턴하고

아니라면 -1을 리턴합니다.

 

이문제를 풀면서 개인적으로 고려하였던 부분으로

연결되지 않은 노드

노드가 2개만 있고 두 노드가 연결된 경우

이 두가지였습니다.

 

우선 연결되지않은 노드는 진입 차수가 0으로 잡혀 아래 코드에서 어디에서도 사용되지않다가 마지막 계산에서 해당 노드의 가중치가 0인지만 체크하여 해결하였고

 

노드가 2개만 있고 두노드가 연결된 경우는 두 노드 모두 진압차수가 1이기 때문에 방문처리를 큐에서 해당 노드를 처리할때 하여서 앞선 노드가 실행되면 뒤 노드의 진입차수가 0이 되면서 위의 연결되지않은 노드와 같은 처리가 되도록 하였습니다. 

import java.util.*;

class Solution {
    public long solution(int[] a, int[][] edges) {

        // 모든 간선의 가중치 값의 합이 0이 아닌 경우
        if(Arrays.stream(a).sum() !=0) return -1;

        long answer = 0;
        int[] indegree = new int[a.length]; // 진입차수 배열
        boolean[] visited = new boolean[a.length]; // 방문 여부
        long[] temp = new long[a.length]; // a를 long으로 변환하기 위한 배열
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

        // a를 long 배열로 변환
        for(int i = 0; i < a.length; i++) {
            temp[i] = a[i];
        }

        // a 의 길이만큼 graph에 추가
        for(int i = 0; i < a.length; i++) {
            graph.add(new ArrayList<>());
        }

        // graph에 간선 셋팅 && 진입차수 셋팅
        for(int i = 0; i < edges.length; i++) {
            int nodeA = edges[i][0];
            int nodeB = edges[i][1];

            graph.get(nodeA).add(nodeB);
            graph.get(nodeB).add(nodeA);

            indegree[nodeA]++;
            indegree[nodeB]++;
        }

        // 진입 차수가 1인 경우
        // 진입차수가 1인 경우 연결된 노드가 1개로
        // 노드는 반드시 연결된 단하나의 노드에 모든 가중치를 넘겨줘야함
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < indegree.length; i++) {
            if(indegree[i] == 1) {
                q.offer(i);
            }
        }

        while(!q.isEmpty()) {
            int now = q.poll();
            visited[now] = true;

            ArrayList<Integer> nodes = graph.get(now);
            for(int i = 0 ; i < nodes.size(); i++) {
                int curr = nodes.get(i);
                if(visited[curr]) continue;
                indegree[curr]--;
                temp[curr] += temp[now];
                answer += Math.abs(temp[now]);
                temp[now] = 0;

                if(indegree[curr] == 1) {
                    q.offer(curr);
                }
            }
        }

        // temp는 간선들의 가중치 값 배열로 전부 0이 아니라면 불가능
        for(int i = 0; i < temp.length; i++) {
            if(temp[i] != 0) {
                answer = -1;
                break;

            }
        }
        return answer;
    }
}