📒활용개념

1.DFS
2. 레퍼런스

• &를 사용하여 변수를 사용하는 것이다.
• 이름이 있는 메모리 공간에 이름을 하나 더 붙이는 것이다.
• 상수가 올 수 없고 반드시 변수명이 와야하며, 선언과 동시에 초기화 되어야 한다.
• 함수 내에서 외부에 존재하는 변수에 접근하기 위해서 사용한다.

3. vector.resize() 함수

📌문제설명

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

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

• 2<=n<=100
• wires는 길이가 n-1인 정수형 2차원 배열

📌구현

#include <string>
#include <vector>

using namespace std;

vector<vector<bool>> map;					//연결 유무를 판단하는 vector
int answer;

void dfs(int index, int &cnt){				//어떤 선을 끊었을 때의 양쪽의 트리의 송전탑 개수를 세는 dfs함수
    cnt++;
    for(int i=1; i<map.size(); i++){
        
        if(map[index][i]){
            map[index][i]=false;			//이미 지나온 송전탑은 false
            map[i][index]=false;
            
            dfs(i, cnt);
            
            map[index][i]=true;
            map[i][index]=true;
        }
    }
}

void getDiff(int from, int to){				//양쪽 트리에서의 송전탑 차이를 계산하는 함수
    int cnt1=0;
    int cnt2=0;
    
    dfs(from, cnt1);
    dfs(to, cnt2);
    
    if(abs(cnt1-cnt2)<answer){
        answer=abs(cnt1-cnt2);
    }
}

int solution(int n, vector<vector<int>> wires) {
    int N=n;
    answer = n;
    map.resize(n+1);
    
    for(int i=1; i<n+1; i++){
        for(int j=0; j<n+1; j++){
            map[i].push_back(false);				//map초기화
        }
    }
    
    for(int i=0; i<wires.size(); i++){
        map[wires[i][0]][wires[i][1]]=true;
        map[wires[i][1]][wires[i][0]]=true;
    }
    
    for(int i=0; i<wires.size(); i++){
        map[wires[i][0]][wires[i][1]]=false;
        map[wires[i][1]][wires[i][0]]=false;
        
        getDiff(wires[i][1], wires[i][0]);
        
        map[wires[i][0]][wires[i][1]]=true;
        map[wires[i][1]][wires[i][0]]=true;
    }
    
    return answer;
}

📌주의점

• 숫자가 크지 않아서 dfs를 활용하여 문제를 풀 수 있다.
• 레퍼런스를 이용하지 않으면 전역변수의 수가 많아질 수 있다.
• 이중vector를 활용한 연결유무 표시.(map)
• vector.resize() 함수를 통해 map의 크기를 결정한다.

처음 문제를 풀 때는 시간복잡도를 고민해서 dfs를 사용하면 안된다고 생각했지만, 크기가 작기 때문에 dfs를 통해서 모든 경로를 확인해도 시간복잡도가 커지지 않는다.