[프로그래머스/Level3] 모두 0으로 만들기 (JAVA)

📖 문제

프로그래머스

 

 

💡  풀이 방식

• DFS / BFS + 그리디

필요 자료구조
- 인접 정점 정보 저장할 ArrayList 배열
- 정점 방문 표시할 boolean형 배열
- 가중치 정보 저장할 long형 배열

 

1. 배열 a의 전체 합한 값이 0인지 확인한다. 0이 아니라면 -1을 리턴한다.

2. 인접 정보를 저장할 ArrayList 배열을 생성해 인접한 값들 정보를 저장한다.

3. 방문 표시 배열과 DFS를 통해 leaf 노드까지 쭉 탐색했다가 차례대로 올라온다. (탐색 방향 : 위에서 아래)

4. 부모 정점은 자식 정점의 value을 받아 자신의 값에 더하고 (= 가중치 옮기기. +1,-1 연산한 효과), 모든 정점은 자신의 value의 절댓값을 answer에 합산한다.

 

가중치를 업데이트하면서 모든 노드를 0으로 만들 수 있다.

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static int[] a;
    static int[][] edges;
    
    static long answer = 0;
    static long[] longArr;
    
    static List<Integer>[] A;
    static boolean[] visited;
    
    public long solution(int[] a, int[][] edges) {
        this.a = a;
        this.edges = edges;
        
        longArr = new long[a.length];
        A = new ArrayList[a.length];
        visited = new boolean[a.length];
        
        long sum = 0;   // a 배열의 전체 합
        for(int i = 0 ; i < a.length ; i++) {
            sum += a[i];
            A[i] = new ArrayList<>();
            longArr[i] = a[i];
        }
        
        // 전부 더해서 0이 안 되면 -1 리턴
        if(sum != 0)    return -1;
        
        // 인접 정보 저장
        for(int i = 0 ; i < edges.length ; i++) {
            A[edges[i][0]].add(edges[i][1]);
            A[edges[i][1]].add(edges[i][0]);
        }
        
        dfs(0);
        
        return answer;
    }
    
    private static long dfs(int v) {
        visited[v] = true;
        
        for(int i = 0 ; i < A[v].size() ; i++) {
            int next = A[v].get(i); // 인접 노드 가져오기
            
            if(!visited[next])
                longArr[v] += dfs(next);    // ⭐ dfs로 인접한 노드로부터 가중치 업데이트 (+1, -1 연산 효과. )
        }
        
        answer += Math.abs(longArr[v]); // ⭐ 현재 노드에서 이동한 값만큼 더하기
        
        return longArr[v];
    }
}

 

 

 

➕ 다른 풀이 방식

BFS/위상 정렬을 활용한 풀이 : 트리를 리프 노드부터 거꾸로 탐색 (탐색 방향 : 아래에서 위. 출제의도는 이거)

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

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

 

---

💦 어려웠던 점

- DFS함수에서 인접 노드 가져올 때 향상형 for문 썼더니 TC 2개에서 런타임 에러 떴다

- 어떤 점부터 시작해야할지 생각을 하지 못 했는데 그냥 0이나 아무 점에서부터 모든 점을 탐색하기만 하면 되는 것이었다. (탐색 방향은 상관X)

- +1,-1 연산을 매번 해줘야하나 했는데 이건 가중치를 이동시킨 값을 활용하면 되었다.

 

 

🧐 새로 알게 된 내용

- 목표 노드를 하나 정해두고 남겨진 리프 노드에서부터 목적지 노드까지 가중치 계산해 연산 횟수 누적시켜 한 번에 탐색으로 끝내는 방법

- +1, -1하는 것과 같은 효과를 갖는 가중치를 이동시키는 아이디어 (..)

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

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

 

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