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

문제 링크

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

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

풀이

전체적인 풀이 과정은 다음과 같다.

1. 입력 받은 edges 배열을 바탕으로 각 노드의 인접 노드 리스트, 인접 노드 개수 배열을 초기화
2. 리프노드 (인접 노드 개수가 1개)만 우선적으로 큐에 입력
3. BFS 탐색을 통해 해당 노드의 값을 인접 노드에 넘기면서, 해당 인접 노드의 인접 노드 개수 카운트를 1 감소
4. 해당 인접 노드 또한 인접 노드 개수가 1일 때만 큐에 입력하여 탐색 반복

 처음 문제를 봤을 땐 문제 자체가 이해가 가지 않았지만, 문제가 요구하는 바는 "어느 한 노드의 값을 다른 한 노드에 더하면서, 이를 반복해 전체 노드가 모두 0이 되게 만들 수 있는가"를 물어보는 것이다.

 결국 전체 노드가 0이 되게 하려면, 트리에 퍼져 있는 모든 값들을 하나의 노드로 모두 몰아 넣은 후, 해당 최종 노드의 값이 0인지를 확인하면 된다. 여기서 발생하는 문제는 값을 몰아 넣을 노드가 어디인 지를 정해야 하는 데, 정해지는 트리의 특성 상 루트 노드 같은 중심 노드가 주어지지는 않기 때문에 이를 특정하기가 힘들다.

 그렇기에 대신 말단 노드부터 차례차례 값을 옮기는 방법으로 풀이를 달리 했는데, 리프 노드부터 값을 그 부모 노드로 이동하고, 해당 리프 노드가 없다는 가정에서 또 다시 트리의 리프 노드들의 값을 그 부모 노드로 넘기다 보면, 어느 순간 하나의 노드로 값이 모일 거라는 방향으로 풀이 방식을 잡고 이를 구현했다.

 입력받은 edges 배열을 통해 각 노드들의 인접 노드 리스트, 인접 노드 개수 배열을 만든 다음, 인접 노드 개수가 1개인 것만 큐에 담은 후 BFS 탐색을 진행한다. 하나의 탐색에서 값을 부모 노드로 옮기고, 해당 값의 절대값이 횟수를 의미하기 때문에 해당 값을 따로 answer 변수에 더한다. 이후 부모 노드의 인접 노드 개수 값을 1 감소 시켜, 이후 해당 부모 노드가 다음 탐색의 리프 노드가 될 수 있게 한 다음, 다음 트리 구조의 말단 노드들을 큐에 넣어 다시 탐색을 하는 방향으로 코드를 구현했다.

 추가적으로 a배열 자체에 값을 더하는 경우가 많다보니 int 배열의 크기를 넘는 경우가 발생해, 이를 다시 long 타입의 배열로 복사하는 과정을 거친 후 연산에 활용했다.

 

class Solution {
    public long solution(int[] a, int[][] edges) {
        long answer = 0, sum = 0;
        int totalNodesCount = a.length; //전체 노드 개수
        long[] copyA = new long[totalNodesCount]; //int 배열 a -> long 배열로 복사
        Queue<Integer> q = new LinkedList<>(); //BFS 탐색용 큐

        for (int i = 0; i < totalNodesCount; i++)//long 배열로 옮기며 노드 값 총합도 계산
            sum += copyA[i] = a[i];

        if (sum != 0) //0이 아니면 애초에 과정이 불가능
            return -1;

        ArrayList<Integer>[] adjacentNodes = new ArrayList[totalNodesCount]; //인접 노드 리스트
        int[] adjacentNodesCount = new int[totalNodesCount]; //인접 노드 개수
        boolean[] visited = new boolean[totalNodesCount]; //중복 방문 방지용

        for (int i = 0; i < totalNodesCount; i++) //인접 노드 리스트 초기화
            adjacentNodes[i] = new ArrayList<>();

        for (int i = 0; i < edges.length; i++) { //값 채우기
            ++adjacentNodesCount[edges[i][0]];
            ++adjacentNodesCount[edges[i][1]];
            adjacentNodes[edges[i][0]].add(edges[i][1]);
            adjacentNodes[edges[i][1]].add(edges[i][0]);
        }

        for (int i = 0; i < totalNodesCount; i++) { //리프노드(인접 노드 1개)만 큐에 입력
            if (adjacentNodesCount[i] == 1)
                q.add(i);
        }

        while (!q.isEmpty()) { //BFS 탐색
            int nowNode = q.remove();

            visited[nowNode] = true;
            long value = copyA[nowNode];

            for (int i = 0; i < adjacentNodes[nowNode].size(); i++) { //인접 노드에 값 전달
                int nextNode = adjacentNodes[nowNode].get(i);

                if (!visited[nextNode]) {
                    --adjacentNodesCount[nextNode];
                    copyA[nextNode] += value;
                    copyA[nowNode] = 0;
                    answer += Math.abs(value);

                    if (adjacentNodesCount[nextNode] == 1) {
                        q.add(adjacentNodes[nowNode].get(i));
                    }

                    break;
                }
            }
        }

        return answer;
    }
}

결과