선밥의 공부하는 블로그

모두 0으로 만들기

문제 링크

모두 0으로 만들기

분석

가중치가 존재하는 트리 구조의 그래프가 주어집니다.
이 트리의 모든 점들의 가중치를 0으로 만들고자합니다.
만약 만들 수 없는 경우 -1을 반환하고, 만들 수 있는 경우 최소 횟수를 반환해야합니다.

a는 트리의 각 점에 대한 가중치를 의미하며, a[i]는 i번 정점의 가중치입니다.

임의로 연결된 두 점을 선택하여 한쪽은 1을 증가시키고, 한쪽은 1을 감소합니다.
즉, 한 정점에서 이웃 정점으로 값을 이동할 수 있으며, 이동한 수의 절댓값만큼 비용이 들게됩니다.

a배열의 전체 합이 0이어야 모든 점들의 가중치를 0으로 만들 수 있습니다.

트리 구조의 그래프이므로, 싸이클이 없으며 하나의 루트에서 모든 노드에 도달할 수 있습니다.

풀이

#include <vector>
#include <cmath>

using namespace std;

// 총 이동 비용을 저장할 전역 변수
long long answer = 0;
// 트리 구조를 표현할 인접 리스트
vector<vector<int>> graph;
// DFS 방문 여부를 기록할 배열
vector<bool> visited;
// 각 노드의 현재 weight값으로, DFS를 통해 상위 노드로 이동시키며 값이 변한다.
vector<long long> weights;

// 현재 노드에서 자식 노드들을 탐색하고, 값을 상위 노드로 보냅니다.
long long dfs(int nodeIndex)
{
    // 현재 노드를 방문 처리
    visited[nodeIndex] = true;
    
    // 연결된 모든 이웃 노드들에 대해 반복
    for (int next : graph[nodeIndex])
    {
        // 방문하지 않은 자식 노드에 대해서만 재귀 호출
        if(!visited[next])
        {
            // 자식 노드에서 올라온 값을 받는다.
            long long childWeight = dfs(next);
            
            // 자식 노드에서 받은 값을 현재 노드에 누적
            weights[nodeIndex] += childWeight;

            // 이동한 값의 절댓값만큼 비용이 발생하고, 해당 비용 누적
            answer += abs(childWeight);
        }
    }
    
    // 현재 노드의 값을 반환하여 부모에게 전달
    return weights[nodeIndex];
}

long long solution(vector<int> a, vector<vector<int>> edges) {
    // 주어진 모든 값들의 총합을 구한다.
    long long totalSum = 0;
    for (int e : a)
    {
        totalSum += e;
    }
    
    // 전체 합이 0이 아니라면 절대로 모든 값을 0으로 만들 수 없다.
    if (totalSum != 0)
    {
        return -1;
    }
    
    // 전역 변수 초기화
    int n = a.size();
    graph.resize(n);
    visited.resize(n, false);
    weights.assign(a.begin(), a.end());
    
    // 트리 구성
    for (auto& edge : edges)
    {
        int u = edge[0];
        int v = edge[1];
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    // 루트 노드(0번 노드)부터 DFS 탐색
    dfs(0);
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n)$입니다.

  • 주어진 모든 값들의 총합을 구하는 반복문 $O(n)$
  • 트리(그래프)를 구성하는 반복문 $O(n)$
  • DFS 호출 $O(n)$
  • $O(n) + O(n) + O(n)$

공간 복잡도는 $O(n)$입니다.

  • 인접 리스트로 표현한 그래프 vector<vector<int>> graph $O(n)$
  • 방문 여부를 저장한 vector<bool> visited $O(n)$
  • 노드의 weight값 vector<long long> weights $O(n)$
  • DFS 깊이 $O(n)$
  • $O(n) + O(n) + O(n) + O(n)$
테스트 성능

테스트 1 〉 통과 (0.01ms, 4.18MB)
테스트 2 〉 통과 (0.01ms, 4.18MB)
테스트 3 〉 통과 (20.68ms, 69.7MB)
테스트 4 〉 통과 (91.87ms, 88.2MB)
테스트 5 〉 통과 (78.67ms, 88.2MB)
테스트 6 〉 통과 (19.27ms, 69.7MB)
테스트 7 〉 통과 (136.81ms, 95.7MB)
테스트 8 〉 통과 (141.30ms, 93.8MB)
테스트 9 〉 통과 (19.03ms, 69.6MB)
테스트 10 〉 통과 (65.13ms, 90.4MB)
테스트 11 〉 통과 (137.52ms, 87.9MB)
테스트 12 〉 통과 (20.73ms, 69.6MB)
테스트 13 〉 통과 (49.63ms, 89.3MB)
테스트 14 〉 통과 (52.78ms, 89.3MB)
테스트 15 〉 통과 (19.99ms, 69.8MB)
테스트 16 〉 통과 (138.82ms, 91.8MB)
테스트 17 〉 통과 (89.96ms, 90.3MB)
테스트 18 〉 통과 (40.17ms, 89.2MB)

Programmers 카테고리 내 다른 글 보러가기

댓글남기기

최근 글