2-2. 완전 탐색 [프로그래머스 전력망을 둘로 나누기]

1. 관련 문제 🎯

문제 : [프로그래머스] 전력망을 둘로 나누기 💡
난이도 : LEVEL 2

2. 문제 소개 🧩

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

• 아래의 예시를 살펴보면, 하나의 트리 형태로 되어 있다.
  이때, 4번과 7번을 끊어내면 4번을 기준으로 6개, 7번을 기준으로 3개를 가진 2개의 네트워크가 만들어진다.
  

그림 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/86971

3. 문제 풀이 🖌️

1. 송전탑 연결에 대한 정보를 인접 리스트 형태의 그래프로 입력받는다.
2. 하나씩 연결을 끊고 연결을 끊은 2개의 노드를 기준으로 DFS를 사용하여 각각의 네트워크 당 송전탑의 개수를 센다.
3. 각각의 네트워크의 송전탑의 개수의 차이 절대값이 최소값인지 확인하며 위의 과정을 반복한다.

3-1. 송전탑 연결에 대한 정보를 인접 리스트 형태의 그래프로 입력받는다.

• 방향이 따로 정해져 있지 않으므로 양방향으로 그래프를 입력받는다.

for(int i=0; i<wires.size(); i++){
	int first = wires[i][0];    
    int second = wires[i][1];
	graph[first].push_back(second);
	graph[second].push_back(first);
}

3-2. 하나씩 연결을 끊어보면서 연결을 끊은 2개의 노드를 기준으로 DFS를 사용하여 각각의 네트워크 당 송전탑의 개수를 센다.

* DFS를 수행하는 기준

• ☝️ 이때, 가장 중요한 건 "연결을 끊은 2개의 노드를 기준"으로 DFS를 한다는 점이다!
• 해당 문제를 풀고 나서, 다른 사람들의 풀이를 봤는데,,, DFS를 1부터 n까지 하는 풀이도 볼 수 있었다!!
• 그러나, 해당 문제는 하나의 트리에서 하나의 연결만을 끊는다는 것을 가정했기 때문에, 항상 하나의 연결을 끊게 되면 해당 2개의 노드를 기준으로 2개의 네트워크가 만들어진다는 것은 확실하다!!
• 따라서, DFS를 2개의 노드에만 수행하면, 시간을 단축할 수 있다~!
  

* 연결을 끊는 방법

• 전선 연결을 끊을 때, 이전에는 연결 리스트에서 아예 제외시키고 나중에 다시 넣는 방식으로 하려고 했다!!
  ➡️ 모든 케이스를 통과하기는 하지만, 아래의 사진처럼 속도가 느렸다. ⏰
• 따라서, 방문 여부를 기록하는 check[ ]배열을 사용하여 전선 연결을 끊는 경우, 해당 노드를 방문을 했다고 true로 변경해준다.
  ➡️ 그러면 DFS를 도는 경우 이미 방문을 했다고 표시해주었으므로, 연결은 되어 있지만 check[next]이 false가 아니기 때문에 해당 노드는 방문하지 않아서 연결 리스트에서 제외하는 경우와 동일하게 동작한다.

1) 직접 연결리스트에서 지우고 넣은 경우

int first = wires[i][0];    int second = wires[i][1];
//전선 연결 끊기
graph[first].erase(graph[first].begin());   
graph[second].erase(graph[second].begin());

...

//전선 연결 원상 복구
graph[first].push_back(second); 
graph[second].push_back(first);
}

2) 방문 여부를 사용한 경우

memset(check,false,101);	//전선 연결 원상 복구
int first = wires[i][0];    int second = wires[i][1];
check[first] = true; check[second] = true;    //전선 연결 끊기

3-3. 각각의 네트워크의 송전탑의 개수의 차이 절대값이 최소값인지 확인하며 위의 과정을 반복한다.

int dfs(int here, int cnt){
    check[here] = 1;
    for(int i=0; i<graph[here].size(); i++){
        int next = graph[here][i];
        if(check[next] == 0){
            cnt = dfs(next, cnt+1);	//cnt : 연결된 송전탑의 개수
        }
    }
    return cnt;
}
...

 for(int i=0; i<wires.size(); i++){
	memset(check,false,101);	//전선 연결 원상 복구
	int first = wires[i][0];    int second = wires[i][1];
	check[first] = true; check[second] = true;    //전선 연결 끊기
	int var1 = dfs(first, 0);   int var2 = dfs(second, 0);
	answer = min(abs(var1-var2), answer);
}

4. 전체 코드 🔑

#include <string.h>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

vector<int> graph[101];
bool check[101];
int num1 = 0;

int dfs(int here, int cnt){
    check[here] = 1;
    for(int i=0; i<graph[here].size(); i++){
        int next = graph[here][i];
        if(check[next] == 0){
            cnt = dfs(next, cnt+1);
        }
    }
    return cnt;
}

int solution(int n, vector<vector<int>> wires) {
    int answer = 100;
    
    for(int i=0; i<wires.size(); i++){
        int first = wires[i][0];    int second = wires[i][1];
        graph[first].push_back(second);
        graph[second].push_back(first);
    }
    
    for(int i=0; i<wires.size(); i++){
        memset(check,false,101);
        int first = wires[i][0];    int second = wires[i][1];
        check[first] = true; check[second] = true;    //전선 연결 끊기
        int var1 = dfs(first, 0);   int var2 = dfs(second, 0);
        answer = min(abs(var1-var2), answer);
    }
    
    return answer;
}

5. 결과 🏆