C++:: 프로그래머스 < 전력망을 둘로 나누기 >

기존 dfs풀이 방식으로 접근을 하려했다가 형식이 달라져야하는 문제여서 생각이 조금 필요했다. 풀이의 근본적인 개념은 송전탑에 방문을 했는지를 체크해주며 방문하지 않았다면 전선에 연결된 다른 송전탑으로 재귀를 타며 방문을 표기해주는 방식이다. 이렇게 하면 방문한 송전탑과 그렇지 않은 것으로 나뉘여지는데 이값들의 차의 절대값중 가장 작은값이 구하고자하는 답이다.

#include <string>
#include <vector>
#include <cmath>
using namespace std;

int answer = 100;//정답의 최대값은 98이긴하지만 대충 100으로 두었다.
vector<bool> vis(101);//송전탑 방문배열

void dfs(int idx, vector<vector<int>> wires)
{//idx는 방문한 송전탑 번호이다.
    vis[idx] = true;//방문 체크
    for(int i=0;i<wires.size();i++)
    {//wires배열을 탐색하며 idx번의 송전탑이 들어있는지 체크
    	// idx번의 송전탑이 들어있고 연결된 다른쪽 송전탑이 아직 방문하지 않았다면
        if (wires[i][0] == idx && !vis[wires[i][1]]) dfs(wires[i][1], wires);
        else if (wires[i][1] == idx && !vis[wires[i][0]]) dfs(wires[i][0], wires);
    }  
}

int solution(int n, vector<vector<int>> wires)
{
    for(int i=0;i<wires.size();i++)
    {
        int res = 0;
        vector<vector<int>> tmp(wires);
        fill(vis.begin(),vis.end(),false);// 방문 배열 초기화
        tmp.erase(tmp.begin() + i);// 전선을 끊어줌
        dfs(tmp[0][0], tmp);
        for(int i=1;i<=n;i++) if (vis[i]) res++;
        answer = min(answer, abs(res - (n-res)));
    }
    return answer;
}