[프로그래머스] 모두 0으로 만들기 C++ (Lv.3)

 

 

 

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/76503?language=cpp 

프로그래머스

 

이번 문제는 dfs 문제였습니다.

 

 

 

 

 

📝 문제 풀이 

1. 연산을 위한 weight 벡터를 생성하여 a 벡터와 동일하게 초기화

2. info 벡터에 점들의 연결 정보를 저장

3. 루트 노드를 0으로 시작하여 dfs 수행 (루트 노드의 부모 노드는 자기 자신)

• 현재 노드와 연결된 노드가 부모 노드가 아니라면 dfs 수행
• 더 이상 탐색할 노드가 없다면 (리프 노드에 도달했다면) ⭐️

        ➡️ 실제 연산 (부모 노드의 가중치에 현재 노드의 가중치 더하기)

        ➡️ 연산 횟수 계산 (현재 노드의 가중치만큼의 행동을 하기 때문)

4. dfs 종료 후 weight[0] != 0이라면, 모든 점들의 가중치를 0으로 만들 수 없다는 의미이므로 -1 반환

 

 

 

 

👩🏻‍💻 C++ 코드

#include <string>
#include <vector>
#define MAX 300000

using namespace std;

long long answer = 0;
long long weight[MAX];
vector<vector<int>> info(MAX);

void dfs(int node, int parent) {
    for (int i=0; i<info[node].size(); i++) {
        if (info[node][i] != parent) {
            dfs(info[node][i], node);
        }
    }
    
    weight[parent] += weight[node]; // 부모 노드의 가중치에 현재 노드의 가중치를 더해 나감 (현재 노드의 가중치는 0으로 만들었다고 가정)
    answer += abs(weight[node]); // 현재 노드의 가중치만큼의 행동을 함
}

long long solution(vector<int> a, vector<vector<int>> edges) {
    for (int i=0; i<a.size(); i++)
        weight[i] = a[i];
    
    for (auto edge: edges) {
        info[edge[0]].push_back(edge[1]);
        info[edge[1]].push_back(edge[0]);
    }
    
    // 현재 노드와 부모 노드
    dfs(0, 0);
    
    if (weight[0] != 0) answer = -1;
    return answer;
}

 

프로그래머스 - 결과 화면