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

다나·2023년 2월 3일

DFS 완전 탐색

코딩테스트 스터디

목록 보기

16/32

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. 문제 풀이 🖌️

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

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

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

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;
}