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

 

 

문제

문제 설명

 

풀이

 

[풀이]

 

문제를 보면 송전탑의 개수가 최대 100개다. 그러므로 송전탑의 구조가 트리 구조이기 때문에, 연결 부위를 한번 씩 끊어서 완전탐색해도 된다.

 

하지만, 연결된 a와 b를 끊을 때마다 하위 트리를 계산하는 것은 비효율 적이라 생각해서, 1번 송전탑을 부모 노드로 생각하고, 1번 송전탑과 연결된 노드들을 자식으로 해, 모든 하위 노드의 수를 구하도록 했다.

​

​

[아이디어 정리]

1. 1번 송전탑을 부모 노드로 정한다.

​

2. 자식노드의 하위 원소 개수들을 합쳐서 부모노드의 하위 원소 개수들을 구한다.

ex) 1의 자식노드가 [2,3] 이라고 가정하면,

1의 하위 원소 개수 = [자기 자신+2의 하위 원소 개수 + 3의 하위원소 개수]로 표현할 수 있다.

​

요약하면 자식들의 하위 원소 개수를 재귀적으로 구하고, 구할 때마다 송전탑의 개수를 비교해 송전탑 수의 차이가 최소였는지 계산했다.

 

 

Code

 

 

#include <string>
#include <vector>
using namespace std;

vector<vector<int>>visited;
vector<vector<int>>graph;
vector<int> answer;
int dap=100;
int realN;

int calc(int node)
{
    int nodeCnt=1;    
    for (int i=0; i<graph[node].size(); i++)
    {
        if (!visited[node][graph[node][i]])
        {
            visited[node][graph[node][i]]=true;
            visited[graph[node][i]][node]=true;
            nodeCnt+=calc(graph[node][i]);    
        }
    }
    answer[node]=nodeCnt;
    if (dap>abs((realN-answer[node])-answer[node]))
    {
        dap=abs((realN-answer[node])-answer[node]);
    }
    return answer[node];
}

int solution(int n, vector<vector<int>> wires) {
    realN=n;
    vector<int> a(n+1,false);
    vector<int> b;
    answer=vector<int>(n+1,0);
    for (int i=0; i<n+1;i++)
    {
        visited.push_back(a);
        graph.push_back(b);
    }    
    for (int i =0; i<wires.size(); i++)
    {
        graph[wires[i][0]].push_back(wires[i][1]);
        graph[wires[i][1]].push_back(wires[i][0]);
    }
    calc(1);
    return dap;
}

 

---

 

 

쉬운 문제들은 풀이를 고민할 시간에 완전탐색으로 바로 푸는게 나아 보이는데...

 

프로그래머스