코딩테스트 -- 모두 0으로 만들기 - (프로그래머스 / C++)

프로그래머스

 

문제!

---

각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다.

• 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한쪽은 1 감소시킵니다.

하지만, 모든 트리가 위의 행동을 통하여 모든 점들의 가중치를 0으로 만들 수 있는 것은 아닙니다. 당신은 주어진 트리에 대해서 해당 사항이 가능한지 판별하고, 만약 가능하다면 최소한의 행동을 통하여 모든 점들의 가중치를 0으로 만들고자 합니다.

트리의 각 점의 가중치를 의미하는 1차원 정수 배열 a와 트리의 간선 정보를 의미하는 edges가 매개변수로 주어집니다. 주어진 행동을 통해 트리의 모든 점들의 가중치를 0으로 만드는 것이 불가능하다면 -1을, 가능하다면 최소 몇 번만에 가능한지를 찾아 return 하도록 solution 함수를 완성해주세요. (만약 처음부터 트리의 모든 정점의 가중치가 0이라면, 0을 return 해야 합니다.)

프로그래머스!

 

---

요약하면

각 노드의 값들이 존재하고 서로 연결하는 간선을 줄테니 값을 이동시켜서 모두 0이되도록 만들어라! 하는 문제!

 

  

트리..? 라고 해서 바로 트리를 만들어 볼까도 했지만

그것보다는 2차원 그래프로 만들어 탐색하는 편이 나아보여서 먼저 벡터를 만들어 보았습니다.

 

시작!

 

먼저 간선들을 서로 연결시켜주고

    vector<vector<int>>tree(a.size());//간선연결
    for(vector<int> i : edges){//연결된거 체크
        tree[i[0]].push_back(i[1]);
        tree[i[1]].push_back(i[0]);
    }

 

각 노드의 값들도 저장해주었습니다.

    vector<long long> sum(a.size());//각 칸의 숫자
    for (int i = 0; i < a.size(); ++i){
        sum[i] = a[i];
    }

 

여기서 한 번 막혔던게 0번 노드에서 탐색을 시작하면 아래로 내려갈텐데

 

이 부분에서 값을 어떻게 나누어 줘야 할지 였습니다...

 

하지만 금방 해결했습니다!

 

바로 dfs!

깊이 탐색을 사용하면 값을 들고 내려가는게 아닌 제일 아래부터 다시 올라오는 느낌으로 사용할수있었습니다...

dfs만세..

 

깊이 탐색을 구현해주고

void DFS(vector<vector<int>>& graph, vector<long long>& sum, int now, int parent) {
    
    for (int i = 0; i < graph[now].size(); ++i){
        if (graph[now][i] != parent){
            DFS(graph, sum, graph[now][i], now);
        }
    }
    sum[parent] += sum[now];
    answer += abs(sum[now]); 
}

마지막부터는 노드의 값들을 이동시키며 올라옵시다.

+ answer값도 계속 구해줍시다(몇번 시행하는지!)

 

 

 

그리고 시작점은 무난하게 0부터 시작해주면 끝! (어디든 상관 없어요! 트리라서 어느점이든 시작점 가능!)

DFS(tree, sum, 0, 0);//탐색

 

 

끝내기 전에 예외 처리도 해준다면 완벽!

if (sum[0] == 0){
        return answer; 
    } 
    
    else return - 1;

 

 

 

 

ALL

!#include <string>
#include <vector>
#include <algorithm>
using namespace std;

long long answer = 0;

void DFS(vector<vector<int>>& graph, vector<long long>& sum, int now, int parent) {
    
    for (int i = 0; i < graph[now].size(); ++i){
        if (graph[now][i] != parent){
            DFS(graph, sum, graph[now][i], now);
        }
    }
    sum[parent] += sum[now];
    answer += abs(sum[now]); 
}


long long solution(vector<int> a, vector<vector<int>> edges) {
    
    vector<vector<int>>tree(a.size());//간선연결
    for(vector<int> i : edges){//연결된거 체크
        tree[i[0]].push_back(i[1]);
        tree[i[1]].push_back(i[0]);
    }
    
    
    vector<long long> sum(a.size());//각 칸의 숫자
    for (int i = 0; i < a.size(); ++i){
        sum[i] = a[i];
    } 

    DFS(tree, sum, 0, 0);//탐색
    
    if (sum[0] == 0){
        return answer; 
    } 
    
    else return - 1; 
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!