[Programmers] 전력망을 둘로 나누기

문제링크

Programmers - 전력망을 둘로 나누기

문제

모든 노드가 연결된 트리에서 간선 한 개를 삭제했을 때, 각 분할된 트리가 몇개의 노드를 포함하는지 차이의 최소값을 구하는 문제이다.

풀이

문제 분류 자체가 완전탐색으로 되어 있어서, 접근방법 자체는 쉽게 생각해낼 수 있었다. 간선 하나를 제외하고 탐색하여, 해당 상황에서 트리가 포함하는 노드의 개수를 구한다.

wires는 한 방향으로만 이루어져 있으므로 양방향 그래프로 바꾸어준 뒤 작업을 실행한다.

간선을 삭제하는 작업은 두가지 방법이 있다.
wires[i] 의 첫번째 요소를 a 두번째 요소를 b라고 할 때,

1. a, b의 방문 여부를 true로 설정한 뒤 탐색 시작

2. a에서 탐색을 시작하되, b가 도착 노드인 경우를 제외

1번 방법이 더 깔끔한 것 같다.

이런식으로 모든 간선에 대해 bfs를 한 번씩 진행해서 answer을 도출했다.

더 좋은 풀이(dfs 한 번 사용)

다른 사람풀이를 보면 dfs한 번으로 정답을 구해내는 풀이가 있다.
dfs를 진행하면서, 현재 노드 cur, cur과 연결된 nxt를 볼 때 cur에 연결된 노드의 개수는 nxt와 연결된 노드들의 합과 같다.
즉, dfs로 자식 노드의 연결 개수를 확인하고 해당 값을 이용해 cur과 연결된 자식 노드의 개수를 업데이트 한다.
충분히 생각해낼 수 있는 효율적인 풀이인 것 같다. 다음에 풀 땐 이 방법을 생각해낼 수 있으면 좋겠다.

코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

vector<vector<int>> G;

int bfs(int n, int nx){
    queue<int> Q;
    bool visited[101]; 
    int count = 0;
    for(int i=0; i<101; i++) visited[i] = false;
    Q.push(n); visited[n] = true;
    
    while(!Q.empty()){
        int now = Q.front(); Q.pop();
        count++;
        for(int i=0; i<G[now].size(); i++){
            if(visited[G[now][i]] == false && G[now][i] != nx){
                Q.push(G[now][i]); visited[G[now][i]] = true;
            }
        }
    }
    return count;
}
int solution(int n, vector<vector<int>> wires) {
    int answer = 100;
    G.resize(n+1);
    for(int i=0; i<wires.size(); i++){
        G[wires[i][0]].push_back(wires[i][1]);
        G[wires[i][1]].push_back(wires[i][0]);
    }
    
    for(int i=0; i<wires.size(); i++){
        int count = bfs(wires[i][0], wires[i][1]);
        if(count>n/2) count = n-count;
        answer = min(answer, abs(n-count*2));
    }
    
    return answer;
}