전력망을 둘로 나누기

문제

접근법

wires의 하나의 요소를 삭제를 한 경우에 대하여 그래프를 구현하고 그 그래프의 하나의 요소를 탐색을 하여 check라는 배열에 탐색을 한 것에 대하여 true를 넣어주고 아닌 경우에는 false로 넣어주어 true와 false의 개수의 차이를 구하면 된다고 생각을 하고 문제를 풀었다.

풀이

#include <string>
#include <vector>
#include <unordered_map>
#include <cmath>
#include <iostream>

using namespace std;


void dfs(unordered_map<int,vector<int>> map,int key,bool *check)
{
    
    check[key]=true;
    for(int i=0;i<map[key].size();i++)
    {
        if(check[map[key][i]]==false)
        {
            check[map[key][i]]=true;
            if(map.find(key)!=map.end())
                dfs(map,map[key][i],check);
        }
    }
    

}


// check의 인덱스는 1~7999 까지 있겟죠.

int solution(int n, vector<vector<int>> wires) {
    int answer = 101;
    unordered_map<int, vector<int>> map;

    for(int i=0;i<wires.size();i++)
    {
        for(int j=0; j<wires.size(); j++)
        {
            if(i != j)
            {
                if(map.end()==map.find(wires[j][0]))
                {
                    vector<int> v;
                    v.push_back(wires[j][1]);
                    map.insert(make_pair(wires[j][0],v));

                }
                else
                {
                    map[wires[j][0]].push_back(wires[j][1]);
                }
                
                if(map.end()==map.find(wires[j][1]))
                {
                    vector<int> v;
                    v.push_back(wires[j][0]);
                    map.insert(make_pair(wires[j][1],v));

                }
                else
                {
                    map[wires[j][1]].push_back(wires[j][0]);
                }
            }
            
        }
        
        bool check[101] = {false, };
        
        if(i == 0) dfs(map,wires[1][0], check);
        else dfs(map,wires[0][0],check);
        
        
        int cnt[2] = {0,0};
        for(int l=1;l<=n;l++)
        {
            if(check[l]==true)
                cnt[0]++;
            else
                cnt[1]++;

        }
        
        if(answer > abs(cnt[0]-cnt[1]))
        {
            answer = abs(cnt[0]-cnt[1]);
        }
        
        cout<<cnt[0] << " " <<cnt[1]<<endl;
        
        map.clear();
        
    }
    return answer;
}

/*

n개의 송전탑이 전선을 통해서 트리 형태로 연결됨.

전선 중 하나를 끊어서 전력망 네트워크를 2개로 분할 할 거임.

두 전략망이 갖게 되는 송전탑의 개수가 비슷하게 해야함

n = 송전탑 개수

wires = 어떤 송전탑 끼리 연결되어 있는지는 보여준다.

그래프의 문제이다.

전선 중 하나를 끊는다. 라는 것은 wires의 한 요소가 없어진 것을 이야기한다.

그러면 요소를 하나 사라지게 한 모든 결과를 탐색한다.

*/

풀이

wires의 요소를 하나를 지우고 해시테이블을 통해서 그래프를 구현을 했습니다. 처음에는 이 해시테이블이 송전탑 전부에 대해서 쓰지 않아도 된다고 생각을 했습니다.

그런데 문제가 발생했습니다.
wires의 요소들의 첫번째 인덱스를 기준만으로 key값을 생성하고 value값으로 두번째 인덱스들을 추가해주었습니다.

이렇게 할 경우 그래프의 탐색이 제대로 이루어지지 않았습니다.
예를들어

위와 같은 그래프를 탐색을 한다고 할 때, 첫 시작은 먼저 노드 1을 탐색을 할 것입니다.
그래서 CHECK[1] =TRUE로 값이 변할 것이고, 그다음은 1노드의 값의 첫번째 인덱스인 3을 탐색을 할 것입니다. 그런데 여기서 문제가 발생을 합니다. 3을 탐색을 하려고 보니까 3은 해쉬테이블에 존재하지 않는 KEY값입니다. 그래서 DFS는 일어나지 않고 그저 CHECK[3] = TRUE로 일을 끝내버립니다. 이렇게 되면 노드2는 같이 연결되어 있는 송전탑임에도 2를 포함하지 않고 DFS가 끝나버립니다.

그래서 결론은 그래프를 만들때는 모든 노드에 대해서 연결되어 있는 값들을 추가해야 한다는 것을 알게 됐습니다.