[프로그래머스 2레벨] 전력망을 둘로 나누기 (C++)

 

#include <string>
#include <vector>
#include <climits>
#include <cmath>
#include <cstring> 

using namespace std;

vector<int> v[101];
bool visited[101];

int dfs(int cur) 
{
    visited[cur] = 1;
    int cnt = 1; //카운팅

    for (int next : v[cur]) 
    {
        if (visited[next]) continue;
        cnt += dfs(next);
    }

    return cnt;
}

int solution(int n, vector<vector<int>> wires) {
    int answer = INT_MAX;

    for (auto wire : wires) 
    {
        v[wire[0]].push_back(wire[1]);
        v[wire[1]].push_back(wire[0]);
    }

    for (auto wire : wires) 
    {
        memset(visited, false, sizeof(visited)); // 방문 배열 초기화

        visited[wire[1]] = true; // 한쪽을 방문체크
        int cnt = dfs(wire[0]);  // 나머지 한쪽에서 카운팅
        int diff = abs(n - 2 * cnt); // 두 그룹의 차이 계산
        answer = min(answer, diff);
    }

    return answer;
}

 

dfs나 bfs 알고리즘을 통해 전부 탐색하면서 카운팅을 해주는 문제이다.

우선 양방향으로 연결된 값을 각 방향에 넣어주고 시작한다.

 

이후 방문 배열을 이용해 한쪽은 방문 체크하고 나머지 방향을 기준으로 카운팅을 시작한다.

이를 모든 위치에 대해서 시행하며 카운팅한 값을 토대로 그룹 간 차이가 가장 적은 값을 탐색한다.