[programmers] 전력망을 둘로 나누기

https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

dfs

 

---------------------------------------------------풀이----------------------------------------------------

 

트리 구조이므로, root부터 시작해 트리를 탐색하는 방식으로 진행하였다.

우선, 한 노드를 선택하면, 그 노드를 포함하는 subtree의 크기를 subnode라는 변수에 저장하고,

이 subtree를 제외한 나머지 노드의 개수는 '전체 크기 - subnode'로 구하였다.

이렇게 하면 완벽히 둘로 나눌 수 있고, 나눈 상태에서의 크기 차이를 구해 최솟값을 저장하였다.

#include <string>
#include <vector>
#include <math.h>

using namespace std;

// adj list
vector<int> adj_list[101];
int N;
bool visited[101] = {false, };

int answer = 1000;

// 현재 노드를 루트로 했을 경우에 모든 subtree의 노드 개수 리턴
int dfs(int cur){
    // 자기자신
    int subnode = 0;
    visited[cur] = true;
    for(int i = 0; i < adj_list[cur].size(); i++){
        if(visited[adj_list[cur][i]])
            continue;
        subnode += dfs(adj_list[cur][i]);
    }
    // 현재 트리를 전체 트리에서 분리했을 때 차이를 계산.
    int diff = abs((N - (subnode+1)) - (subnode+1));
    if(diff < answer){
        answer = diff;
    }
    return subnode+1; // 자기 자신을 포함한 개수
}

// 하나의 트리 형태를 두 개로 나누어라. 1~n까지
int solution(int n, vector<vector<int>> wires) {
    N = n;
    for(int i = 0; i < wires.size(); i++){
        adj_list[wires[i][0]].push_back(wires[i][1]);
        adj_list[wires[i][1]].push_back(wires[i][0]);
    }
    dfs(1);
    return answer;
}

 

---------------------------------------------------후기----------------------------------------------------

 

인접리스트를 사용하는게 효과적이었던 문제.

인접 행렬은 탐색 시간이 더 걸렸을 것이다.