전력망을 둘로 나누기

풀이 1 내가 군대에 있었던 22년도 2월에 풀고 기록을 남긴 문제를 다시 해봤다. 저때 당시에 이 문제를 풀어서 굉장히 기뻐했고 그 이후로는 더 이상 안건드리다가 다시 도전했는데 굉장히 쉽게 풀렸다.

추가적으로, 22년도에 풀었던 방식과는 다르게 접근했는데 그 방법이 훨씬 더 효율적이었고 정말 오랜만에 이런 알고리즘류에서 성장을 했다는 느낌이 들었다.

이 문제는 전력망이 통으로 이어져 있을때, 루트 하나를 끊고 그 둘의 차이가 가장 비슷하게 만들면 되는 문제다.
에전에는 이 접근 법을 노드 하나를 끊고 dfs, 노드 하나를 끊고 dfs 이런 방식으로 풀었는데 전혀 안그래도 된다. 말그대로 "경로"에 중점을 두고 루트를 끊으면 정말 쉽게 풀 수 있는 문제다.

루트는 하나만 끊게 되고 나머지는 다 연결되어 있음으로 여러 노드에 탐색을 하지않고 그냥 1부터 탐색해서 전체 노드 수와 빼줘서 값을 구하면 됐다. 예전에 풀이법과 반대로 dfs 는 한번만 하였고 효율적으로 풀었다. 최근에 풀었던 도넛 개수 문제가 떠올라서 쉽게 풀었다.

#include <string>
#include <vector>
#include <bits/stdc++.h> 
using namespace std;

bool visited[101][101]; 

int dfs(int node, vector<vector<int>>& adj, int& tower){
    for(int n : adj[node]){
        if(!visited[node][n] && !visited[n][node]){
            visited[node][n] = true; 
            visited[n][node] = true; 
            dfs(n,adj,tower+=1); 
        }
    }
    return tower; 
}

int solution(int n, vector<vector<int>> wires) {
    int answer = INT_MAX;
    memset(visited,false,sizeof(visited)); 
    vector<vector<int>> adj(n+1); 
    for(vector<int>& v : wires){
        int node1 = v[0], node2 = v[1]; 
        adj[node1].push_back(node2); 
        adj[node2].push_back(node1); 
    }
    
    for(vector<int>& v : wires){
        int node1 = v[0], node2= v[1]; 
        visited[node1][node2] = true;
        visited[node2][node1] = true; 
        int tower = 1; 
        int count1 = dfs(1,adj,tower);
        int count2 = abs(n - count1); 
        answer = min(answer,abs(count1 - count2)); 
        memset(visited,false,sizeof(visited)); 
    }
    return answer;
}