프로그래머스] C++ 위클리 챌린지 9주차

 

 

 

해당 문제는 프로그래머스 코딩테스트 연습에 있는 문제입니다.

아래 링크를 통해 풀 수 있습니다.

 

https://programmers.co.kr/learn/courses/30/lessons/86971

 

 

 

1. 문제

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

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

 

2. 풀이

해당 문제는 그래프를 사용해서 풀 수 있습니다. 저는 각 요소들을 그래프로 만든 후 DFS로 풀었습니다.

 

여기서 중요한 점은 서로 연결된 부분을 어떻게 끊고, 이를 어떻게 증명하느냐가 관건입니다.

 

해당 문제는 사이클이 없는 트리형식의 그래프이므로 가는길만 DFS검색에서 제외 시켜주면 됩니다.

 

즉, 1 <-> 3 번을 끊겠다고 한다면, 1에서 3으로 가는 구간만 검색을 안해주면 됩니다.

 

해당 구간을 제외한 상태에서 DFS로 각 요소들의 갯수를 구하면 1기준으로 탐색했다면 1이 연결된 부분,

3기준으로 탐색했다면 3이 연결된 부분의 갯수를 알 수 있습니다.

 

양쪽다 알 필요가 없는게, n개를 문제에서 주기 때문에 끊긴 한쪽만 구하면 n에서 빼주면 다른쪽이 요소 갯수가 나오게 됩니다.

 

 

3. 코드

#include <string>
#include <vector>

using namespace std;

bool isflag[101];

int dfs(vector<vector<int>>& graph, vector<bool>& isVisit, int idx){
    int result = 0;
    isVisit[idx] = true;
    
    for(auto& next : graph[idx]){
        if(isflag[idx] && isflag[next]) continue;
        if(!isVisit[next]){
            result += dfs(graph, isVisit, next);
            result++;
        }
    }
    
    return result;
}

int solution(int n, vector<vector<int>> wires) {
    int answer = 100000;
    
    vector<vector<int>> graph(n + 1);
    
    for(auto& v : wires){
        graph[v[0]].emplace_back(v[1]);
        graph[v[1]].emplace_back(v[0]);
    }
    
    for(int idx = 1; idx <= n; idx++){
        for(auto next : graph[idx]){
            vector<bool> isVisit(101);
            isflag[idx] = true; isflag[next] = true;
            
            int result = 1 + dfs(graph, isVisit, idx);
            answer = min(answer, abs(n - (result * 2)));
            
            isflag[idx] = false; isflag[next] = false;
        }
    }
    
    return answer;
}