[Programmers, C++]#Level2_전력 망을 둘로 나누기, DFS, 깊이 우선 탐색, 재귀 DFS, 트리, 트리의 DFS

#1. 문제

프로그래머스

 

 

---

 

#2. 풀이

 

1. 트리

[자료구조]#5_트리

트리 자료구조는 그래프의 한 종류로, 노드 간 1:N의 계층 구조를 '순환 구조' 없이 형성하는 비 선형 자료구조입니다.

 

2. DFS

[자료구조]#6_그래프

DFS(깊이 우선 탐색)은 그래프의 모든 정점을 탐색하는 방법 중 하나로, 시작 정점으로부터 더 이상 확장 불가능한 단말 노드에 이르기까지 깊이 우선적으로 탐색하는 방법입니다. 일반적으로, DFS는 재귀 호출 혹은 스택 자료구조를 활용하여 구현 가능합니다.

 

3. 인접 정점으로부터 파생된 서브트리의 노드 개수와 나머지의 차이!

1. 재귀 호출 DFS를 통해 트리의 모든 정점을 탐색합니다.
2. 탐색 과정에서 현재 노드는 '자식 노드'로부터 파생된 서브트리의 총 노드 개수를 재귀호출을 통해 반환받고, 이들을 총 노드 개수와 비교하여 그 차이 값을 도출합니다. 그리고, 이 결과 값을 활용하여 최소 차이 값을 업데이트해줍니다.

 

---

 

#3. 코드

@@ -0,0 +1,63 @@
/*
    @링크: https://school.programmers.co.kr/learn/courses/30/lessons/86971
    @문제: 전력망을 둘로 나누기
    @설명
        1. DFS 재귀 호출
        2. 각 자식 노드들로부터 형성된 서브트리의 노드 갯수와 N(총 정점 개수)의 비교 및 최소 차이 값 업데이트
*/

#include <string>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

vector<vector<int>> graph;
vector<bool> visited;
int ans = INT_MAX;
int total_size;

int dfs(int node)
{
    //@방문 여부
    visited[node] = true;
    //@ + 자기 자신
    int total = 1;

    //@재귀 호출
    for(const auto next : graph[node])
    {
        if(!visited[next])
        {
            int subtree = dfs(next);
            total += subtree;

            ans = min(ans, abs((total_size-subtree) - subtree));
        }
    }

    return total;

}

int solution(int n, vector<vector<int>> wires) {
    int answer;
    total_size = n;

    graph.resize(n+1);
    visited.resize(n+1, false);

    for(int i=0; i<(int)wires.size(); ++i)
    {
        int u = wires[i][0];
        int v = wires[i][1];

        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    dfs(1);

    return ans;
}

 

---