[프로그래머스] - 전력망 둘로 나누기(C/C++)

프로그래머스

[문제 설명]

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• n은 2 이상 100 이하인 자연수입니다.
• wires는 길이가 n-1인 정수형 2차원 배열입니다.
  • wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
  • 1 ≤ v1 < v2 ≤ n 입니다.
  • 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.

---

입출력 예

 

n	wires	result
9	[[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]	3
4	[[1,2],[2,3],[3,4]]	0
7	[[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]]	1

 

---

[문제 풀이]

프로그래머스 완전탐색 탭에 있는 문제이고,

입력의 크기 100이라서 dfs을 이용하여 완전탐색을 해도 풀리는 문제다.

 

반복문을 통해 wires의 원소를 앞에서 부터 하나씩 뺀 나머지를 그래프에 넣고

1번 전력망부터 탐색을 시작한다.

몇번 탐색했는지를 전역변수로 count한다.

둘로 나누어진 전력망 개수의 차이를 최소로 해야한다.

dfs 탐색 후 count값은 첫번째 전력망의 개수이다. 두번쨰 전력망은 dfs를 통해 찾을 필요없이 바로 계산이 가능하다.

첫번째 전력망 : count

두번째 전력망 : (n - count)

두 전력망의 차이 : abs(n - count - count)

두 전력망의 차이가 최소가 되는 값을 answer에 넣어주면 된다.

[코드]

[GitHub]

GitHub - EGyeom/ProblemSolving

코드가 깨끗하고 명확하게 보일진 모르겠지만, 누군가에게 도움이 될 수도.. 있기에..

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> v;
vector<bool> isVisited;
int gCount = 0;

void dfs(int cur)
{
    gCount++;
    if (v[cur].empty())
        return;

    for (const int& nxt : v[cur])
    {
        if (isVisited[nxt] == true) continue;
        isVisited[nxt] = true;
        dfs(nxt);
    }
    return;
}

int solution(int n, vector<vector<int>> wires) {
    int answer = 102;
    for (int i = 0; i < n-1; i++)
    {
        v.clear();
        v.resize(101, vector<int>());
        isVisited.clear();
        isVisited.resize(101, false);
        gCount = 0;
        for (int j = 0; j < n-1; j++)
        {
            if (i == j) continue;
            v[wires[j][0]].push_back(wires[j][1]);
            v[wires[j][1]].push_back(wires[j][0]);
        }
        isVisited[1] = true;
        dfs(1);
        answer = min(answer, abs((n - gCount) - gCount));
        if(answer == 0 ) break;
    }

    return answer;
}