[완전탐색] 송전탑 수 확인

문제

 

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

접근

 

1) 출력

- 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)

2) 개념화

문제의 해 : 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)

- 모든 경우의수를 확인하여 두개의 트리의 수가 적은 값을 도출해내야함.

1. 트리 연결 확인
2. 연결된 엣지를 하나씩 끊기.
 - 연결된 엣지 : wire 배열.

3. 엣지를 끊었을 때 두 서브트리들의 노드 차이 계산
 - 각 서브트리들 간 노드의 수 파악법 ? //BFS로 확인 가능/
4. 노드 차이를 벡터에 넣기.
5. 벡터에서 가장 작은 값 도출.

3) 구현

BFS 사용.

1) 전체 wire수만큼 반복.
2) wire[n] 끊기. sub grpah1 = wire[0][0]부터 bfs // sub graph2 = wire[0][1] 부터 bfs.
3) 두 그래프를 돌아가며 count 증가시키기.
4) 두 count 간의 차를 구하여 벡터이 인가.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <unordered_map>

using namespace std;

// 각 sub node의 수 계산 후 리턴.
int cal_nodecnt(vector<vector<int>> wire,int node)
{
    int num=1;
    queue<int> q;// bfs로 순회시 연결된 노드 추가.
    // vector<int> visited(wire.size()+1,0);// vector로 사용하니 너무 많은 값을 사용해야함. 따라서 map사용하는게 나을듯.
    unordered_map<int,bool> visited;
    for(int i=0;i<wire.size();i++)
    {
        visited[wire[i][0]]=false;
        visited[wire[i][1]]=false;
    }

    q.push(node);

    while(!q.empty())
    {
        int cur_node = q.front();
        q.pop();

        if(visited[cur_node]==false)
            visited[cur_node]=true;
        else
            continue;

        for(auto edge : wire)
        {
            if((edge[0]==cur_node&&visited[edge[1]]==false))
            {
                q.push(edge[1]);
                num++;
            }
            else if(edge[1]==cur_node&&visited[edge[0]]==false)
            {
                q.push(edge[0]);
                num++;
            }
        }
    }

    return num;
}


int solution(int n,vector<vector<int>> wire)
{
    int answer;
    set<int> res;
    for (int i = 0; i < wire.size(); i++)
    {
        int nd_1 = wire[i][0];
        int nd_2 = wire[i][1];
        vector<vector<int>> sub_wire=wire;
        sub_wire.erase(sub_wire.begin() +i);

        int nd1_num = cal_nodecnt(sub_wire,nd_1);
        int nd2_num = cal_nodecnt(sub_wire,nd_2);

        res.insert(abs(nd1_num-nd2_num));
    }

    answer = *min_element(res.begin(),res.end());
    return answer;
}
/*
입출력 예
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

*/
int main()
{
    vector<vector<int>> wire1 {{1,3},{2,3},{3,4},{4,5},{4,6},{4,7},{7,8},{7,9}};
    vector<vector<int>> wire2 {{1,2},{2,3},{3,4}};
    vector<vector<int>> wire3 {{1,2},{2,7},{3,7},{3,4},{4,5},{6,7}};

    cout<<solution(wire1);
    cout<<solution(wire2);
    cout<<solution(wire3);
}

 

 

* 알게 된 내용

 

1) 개념 부족 

 - 개념은 각 node별 BFS 순회를 진행하여 sub graph의 node 수를 구하기로 했음.

 - 그렇게 하기 위해선 현재 노드의 방문 가능한 인접 노드들을 구하고, 해당 인접 node를 queue에 인가해야함.

 - 인접 노드를 구하는 방식은, edge 배열을 순회하여 현재 노드와 인접한 노드를 구하고, 해당 노드에 방문한적이 없어야함.

 

비교 

 => 문제는 edge의[0]이 현재노드일때만 비교하여 전체 경우의 수를 비교하지 못한것.

 => edge의 [0],[1] 모두가 현재 노드일때 상대 원소가 visited 되었는지 확인하고 진행해야함.

 

* 정리

[개념 잡기.]

-> node 기준, edge 배열을 사용하여 인접 node를 구하여, sub graph의 수를 구한다.

-> edge 배열은 순번에 상관있기때문에 배열의 순서에 상관없이 모두 비교 진행해야한다.

 

 

2) erase 메서드

erase 메서드는 반복자를 매개변수로 받는다.

따라서 반복자를 넣어줘야한다.

 

ex) VECTOR.erase(VECTOR.begin())

      VECTOR.erase(find(VECTOR.begin(),VECTOR.end(),erase_component))

 

 

3) set에서의 데이터 접근

 

set은 리스트로 구성되어있기 때문에 인덱스로 원소에 접근이 불가능하다.

따라서 각 원소들의 반복자들에 *연산자를 사용하여 값을 불러올 수 있다.