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

문제 설명

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

문제 풀이

• 예상치 못한 함정으로 살짝 까다로웠던 문제였다.
• 처음 접근은 특정 노드 부터 시작하여 DFS로 풀이하였다. 하지만 최악의 경우 DFS의 depth가 30만까지 갈 수 있기 때문에 stack overflow가 발생하였다. (최대 depth 1만, python이면 좋았을 것을..)
• 접근을 바꾸어 위상 정렬로 풀이하였다.

  • 큐에 진입차수가 1인 지점을 모두 넣어준다.
  • 큐에서 뺴면서 진입차수를 낮추고 결과에 가중치의 절대값을 더해준다.
  • 모든 인접한 노드에 대하여 아래 사항을 수행한다.
    - 진입 차수 0인 지점 건너뜀
    - 진입 차수를 1낮췄을 때 0이면 마지막 노드이므로 결과 도출
    - 해당 노드에 현재 노드의 가중치를 더해준다.
    - 진입 차수를 1낮췄을 떄 1이면 큐에 해당 노드를 넣어준다.

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public List<List<Integer>> map = new ArrayList<>();
    public int[] inDegree;
    public long[] V;
    public int N;

    public long solution(int[] a, int[][] edges) {
        //초기화
        N = a.length;
        V = new long[N];
        inDegree = new int[N];
        for (int i = 0; i < N; i++) {
            map.add(new ArrayList<>());
            V[i] = a[i];
        }
        for (int i = 0; i < edges.length; i++) {
            int from = edges[i][0];
            int to = edges[i][1];
            map.get(from).add(to);
            map.get(to).add(from);
            inDegree[from]++;
            inDegree[to]++;
        }

        //위상 정렬 시작
        //1. 차수 1인 지점 넣어주기
        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < N; i++) {
            if (inDegree[i] == 1)
                q.add(i);
        }

        //2. 위상 정렬 시작
        long result = 0;
        for (int ind = 0; ind < N; ind++) {
            int x = q.poll();
            inDegree[x]--;
            result += Math.abs(V[x]);

            for (int i = 0; i < map.get(x).size(); i++) {
                int y = map.get(x).get(i);
                if (inDegree[y] == 0) continue;
                //종료 조건
                if (inDegree[y] - 1 == 0) {
                    if (V[x] + V[y] != 0)
                        return -1;
                    else
                        return result;
                }
                V[y] += V[x];
                if (--inDegree[y] == 1)
                    q.add(y);
            }
        }
        return 0;
    }
}