[C++로 풀이] 모두 0 으로 만들기 (DFS, 트리) ⭐⭐⭐

📌 모두 0 으로 만들기

난이도 ⭐⭐⭐

🚀 문제

🚀 내 풀이 ⭕

트리를 DFS 로 순회하여 1️⃣ Leaf 노드에 도달할 때까지 깊이 들어간 후 2️⃣ 빠져 나오는 과정에서 가중치를 0 으로 만드는 횟수와 가중치의 합을 더해나가야 한다.

Leaf 노드까지 깊이 들어간 후 되돌아가며 트리를 올라가는 과정에서(= 매 단계마다 재귀 호출 끝내고 돌아온 시점) 노드들의 가중치를 0 으로 만들면서(= 현재 방문 중인 노드를 0 으로 만들고) 올라온다. 최종적으로 루트 노드까지 가중치를 0 으로 만드는데 성공하는 것이 목표이다!

모든 노드의 가중치를 0 으로 만드는 것이고 연결된 두 노드의 한 쪽은 1 증가하고 다른 한쪽은 1 감소시킨다고 하였으니 현재 방문 중인 노드를 0 으로 만들고 0 으로 만들기 위해 빼준 값 만큼을 부모 노드에 몰빵하여 더해주면 된다.

즉, 현재 방문 중인 노드의 부모 노드에 관한 정보도 알고 있어야 한다. DFS 함수 호출하며 깊이 들어가는 과정에서 투 포인터 쓰듯이 이전 방문 노드(=부모 노드)도 함께 업뎃해나간다.

• 부모 노드에 관한 정보도 같이 알고있어야 하는 이유
  • 1️⃣ 현재 방문 중인 노드를 0 으로 만들고 0 으로 만들기 위해 빼준 값 만큼을 부모 노드에 몰빵하기 위해
  • 2️⃣ 부모 노드를 재방문 하지 않기 위하여

---

📌 트리 라는 특성을 생각할 것!

• 루트 노드는 부모 노드는 곧 루트 노드 자신으로 친다. now = parent = 0
• 루트 노드는 딱히 정해져있지 않다.
  • 어느 노드를 루트로 삼든 괜찮다. 왜냐하면 문제에서 이 그래프를 트리 형태로 주었기 때문이다. 트리는 어느 노드든 루트가 될 수 있다.
  • 그냥 편하게 0 지점을 루트로 삼고 이 곳부터 순회를 시작하겠다.
• 방문 체크 배열을 둘 필요는 없다.
  • 그 이유는 마찬가지로 문제에서 이 그래프를 트리 형태로 주었기 때문이다.
  • 트리 형태이기 때문에 DFS 순회시 부모 노드를 제외한 이전에 방문한 노드를 다시 방문할 가능성은 없다.
    • 다만, 현재 방문 중인 노드에서 다음에 방문할 연결된 노드들을 검사할 때, 이 연결된 노드에 부모 노드도 포함되므로 부모 노드가 아닌 노드들만 DFS 로 들어가도록만 걸러주면 된다.
    • 즉, 방문 체크는 오직 이전 노드인 부모 노드인지 아닌지만 체크해주면 된다.
• answer는 1 씩 더하거나 뺀 횟수이기 때문에 부모 정점에 몰빵해준 그 델타값의 절대값을 누적하여 더해주면 된다.

---

먼저 최대한 깊이 들어가고, Leaf 노드부터 되돌아가는 과정의 노드들에서 업데이트

처음 상태는 이렇다. 회색 원은 정점 번호인 a 배열의 인덱스, 노란 원은 해당 정점의 가중치를 표현한다. answer에 1 씩 더하거나 뺸 횟수를 카운팅 할 것이다.

Leaf 노드인 1 번 정점은 이미 가중치가 0 이라 딱히 변화가 없다.

• 현재 방문 중인 노드 👉 4 번 정점
  • 가중치 값이 2
    • 부모 정점의 가중치를 2 만큼 더해주어야 한다. (자기 자신은 -2 되어 0 이 된다고 가정)
    • answer를 abs(2) = 2 만큼 누적하여 더한다.
• 바로 이전 방문 노드(=부모) 👉 3 번 정점
  • 가중치가 1 + 2 = 3 이 되었다.

• 현재 방문 중인 노드 👉 2 번 정점
  • 가중치 값이 2
    • 부모 정점의 가중치를 2 만큼 더해주어야 한다. (자기 자신은 -2 되어 0 이 된다고 가정)
    • answer를 abs(2) = 2 만큼 누적하여 더한다.
• 바로 이전 방문 노드(=부모) 👉 3 번 정점
  • 가중치가 3 + 2 = 5 이 되었다.

• 현재 방문 중인 노드 👉 3 번 정점
  • 가중치 값이 5
    • 부모 정점의 가중치를 5 만큼 더해주어야 한다. (자기 자신은 -5 되어 0 이 된다고 가정)
    • answer를 abs(-5) = 5 만큼 누적하여 더한다.
• 바로 이전 방문 노드(=부모) 👉 0 번 정점
  • 가중치가 -5 + 5 = 0 이 되었다.

최종적으로 answer은 2 + 2 + 5 = 9 가 된다.

---

📌 주의 사항 👉 long long 을 사용해야 한다.

일단 입력 크기가 매우 큰데다, 누적 합 하는 과정을 계속 해서 하고 있기 때문에 int 로 선언할시 오버플로우가 발생할 수 있다. 나는 계속 습관처럼 int로 선언을 하는데 ㅠㅠㅠ 입력 크기가 매우 큰데 합산 하거나 곱하는 과정이 따른다면 반드시 long long으로 선언해야겠구나 하는 생각을 바로바로 할 수 있도록 연습을 해야할 것 같다.

#include <string>
#include <vector>

using namespace std;

long long answer = 0;
// now : 현재 방문 중인 노드,  parent : 바로 이전 노드 (= 부모 노드)
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); // 깊이 들어가고 봄
    // DFS 끝내고 돌아온 이후
    sum[parent] += sum[now]; // 1️⃣ 현재 방문 중인 노드값을 부모 노드에 더하여 몰빵 (현재 방문 중인 노드는 0 이 되었다고 가정)
    answer += abs(sum[now]); // 2️⃣ 1씩 더하거나 뺀 횟수 (위 sum[now]의 절대값을 취하면 된다. 1씩 더하거나 뺀 그 횟수이기 때문에) 
}

long long solution(vector<int> a, vector<vector<int>> edges) {

    vector<long long> sum(a.size()); // long long 버전의 a, 가중치를 Leaf 노드부터 변화시켜가며 올라갈 것. 
    for (int i = 0; i < a.size(); ++i) sum[i] = a[i];

    vector<vector<int>> graph(a.size());
    for (int i = 0; i < edges.size(); ++i) {
        graph[edges[i][0]].push_back(edges[i][1]);
        graph[edges[i][1]].push_back(edges[i][0]);
    }
    
    DFS(graph, sum, 0, 0); // 출발점(루트)는 0 으로 선정. (루트의 부모는 자기 자신)
    
    if (sum[0] == 0) return answer; // 모든 정점을 0 으로 만드는게 가능한 트리라면 sum 의 모든 원소가 0 이 되어 있는 상태여야 한다. 루트 정점만 간단히 체크해보면 됨.
    else return - 1; // 루트 가중치가 0 이 아니라면 이 트리는 모든 정점을 0 으로 만드는게 불가능했던 트리
}

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

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