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

leehyunjon·2022년 11월 3일
0

모두 0으로 만들기 :


Problem


Solve

그림을 그려서 조금 끄적거리다보면서 모든 정점의 가중치를 0으로 만들수 있는 방법이 보입니다.

  • 모든 정점의 가중치 합이 0이 나오지 않는다면 모든 정점의 가중치를 0으로 만들 수 없다.
  • 트리이지만, 정점부터 시작하지 않고 어떤 지점 부터 시작해도 상관없다.
  • 트리의 끝 지점부터 0으로 만들어가며 시작 지점까지 0으로 만들 수 있다. (DFS)
  • 꼭 트리를 구현하지 않아도 된다.

이 4가지를 발견하고 들어가서 문제를 좀더 쉽게 접근할 수 있었습니다.

먼저 각 트리의 정점의 인접리스트를 생성합니다.

그 후, 0번째 정점부터 시작하여 DFS를 시작해줍니다.
인접한 정점으로 이동하면서 인접 정점이 0이 되도록 DFS에서 반환되는 인접 정점의 가중치를 현재 정점의 가중치에 더해줍니다.
이때, 더 이상 탐색할 인접 정점이 없는 트리는 자신의 가중치를 반환해줍니다.

a = [-5,0,2,1,2] / edges = [[0,1],[3,4],[2,3],[0,3]] 으로 예시를 들어보겠습니다.

DFS를 시작할때 0 정점으로 시작하겠습니다.

1.

0 정점에서 인접 정점 1 정점을 탐색한다면 1 정점은 더이상 인접한 정점이 없기 때문에 자신을 반환하게 되고, 0 정점은 자신의 가중치에 1 정점의 가중치 0을 더해줍니다.

그리고 다음 인접 정점인 3 정점으로 이동합니다.

2.

3 정점에서의 인접 정점인 2 정점에 접근합니다. 2 정점은 더 이상 인접한 정점이 없기 때문에 자신의 가중치를 반환하게 되고 3 정점2 정점의 가중치(2)를 더해줍니다.
(현재 3 정점의 가중치 3)

3.

그 다음 3 정점의 인접 정점인 4 정점에 접근합니다. 3 정점도 더 이상 인접한 정점이 없기 때문에 자신의 가중치를 반환하게 되고, 3 정점4 정점의 가중치(2)를 더해줍니다.
(현재 3 정점의 가중치 5)

그 후, 더 이상 인접 정점이 없는 3 정점은 현재 자신의 가중치인 5를 반환합니다.

4.

다시 0 정점으로 돌아와서 3 정점의 가중치인 5를 반환받게 되고 0 정점은 자신의 가중치에 5를 더해줍니다.
그렇다면 0 정점의 가중치는 0이 되므로 해당 트리의 모든 정점은 0이 되게 됩니다.

이 때, 주의할 점이 있습니다.
a의 모든 수가 최소 -1000000, 최대 1000000이고 a의 최대 길이가 300000이기 때문에 가중치가 int크기를 넘어갈 수 있기 때문에 long타입을 사용해주어야 합니다.


Code

class Solution {
    long answer;
    long sum;
    int N;
    long[] longA;
    List<Integer>[] edge;
    boolean[] check;
    public long solution(int[] a, int[][] edges) {
        N = a.length;
        initEdge(a, edges);
        
        //모든 가중치의 합이 0이 되지 않는다면 모든 정점은 0으로 만들 수 없습니다.
        if(sum != 0) return -1;
        
        answer = 0;
        dfs(a, 0);
        
        return answer;
    }
    
    //dfs로 트리 끝까지 이동하고 자식 노드의 값을 자신의 노드값을 더해서 부모 노드에게 반환
    public long dfs(int[] a,int idx){
        long num = a[idx];
        check[idx] = true;
        for(int i=0;i<edge[idx].size();i++){
            int next = edge[idx].get(i);
            if(check[next]) continue;
            num += dfs(a, next);
        }
        
        //for-each를 이용한 반복 (런타임)
        // for(int e : edge[idx]){
        //     if(check[e]) continue;
        //     num += dfs(a, e);
        // }
        
        answer += Math.abs(num);
        return num;
    }
    
    //인접리스트 만들기
    public void initEdge(int[] a, int[][] edges){
        edge = new List[N];
        check = new boolean[N];
        sum = 0;
        for(int i=0;i<N;i++){
            edge[i] = new ArrayList<>();
            sum += a[i];
        }
        
        
        for(int[] e : edges){
            int u = e[0];
            int v = e[1];
            
            edge[u].add(v);
            edge[v].add(u);
        }
    }
}

Result

코드에 for-each문으로 만든 코드가 주석처리 되어있는데.. 다른 테스트케이스도 넣어보고 잘 통과하는데 for-each로 구현을 하면 몇몇 테스트 케이스에서 런타임이 발생합니다.

for-each를 애용하는 편이라 이 부분이 틀릴거라 생각하지 못했는데 for문을 이용해서 사용하니 통과가 되더군요..

이렇게 맞왜틀을 오래 외친 문제는 처음인것 같습니다.. 아직도 왜 for-each문은 런타임이 발생하는지 모르겠습니다..
시간초과면 모를까.. 혹시 의심되는 부분이 있다면 지적해주시면 감사하겠습니다.


Reference

https://dev-note-97.tistory.com/263

profile
내 꿈은 좋은 개발자

0개의 댓글