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

완전탐색

 

N개의 송전탑이 하나의 트리를 구성하며 연결되어 있는데, 간선 하나를 잘라서 두개의 트리로 분리할 때

이 두개의 트리의 송전탑 개수 차가 최소가 되는 그 최소값을 반환하는 문제

 

두 송전탑을 잇는 간선이 이렇게 wires 라는 배열로 주어짐 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]

간선은 한개씩만 주어지지만 양방향 간선임

---

접근방법

 

완전탐색인 만큼..모든 간선을 잘라보면서 두 그래프의 노드 수 차이를 구해보면 된다.

우선 인접행렬을 만들어서 사용했고,

하나의 간선 (1,3) 을 자르면, 1로 시작해서 갈 수 있는 노드들을 모두 센다 큐를 하나 만들어서 bfs처럼 풀었음

근데, 노드를 방문할 때 3이면 방문하지 않음 => 3으로부터 뻣어갈 수 있는 노드들은 방문하지 않음 = 3과의 간선이 끊어졌을 때 1을 루트노드로 하는 트리의 노드 수(ac)를 알게 됨

-> N에서 ac를 빼면 bc(3을 루트노드로 하는 트리의 노드 수)가 되므로

abs(ac-bc = 2ac-n)가 최소가 되는 경우를 구하면 된다.

 

---

소스코드

#include <string>
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

int solution(int n, vector<vector<int>> wires) {
    int answer = n;
    
    vector<vector<int>> adj(n+1);
    for(int i = 0 ; i < wires.size() ; i++){
        int a = wires[i][0];
        int b = wires[i][1];
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    for(int i = 0 ; i < wires.size() ; i++){
        int a = wires[i][0];
        int b = wires[i][1];
        
        int ac = 0; // 각 트리의 노드수
        vector<bool> visit(n+1, false);
        queue<int> q;
        q.push(a);
        while(!q.empty()){
            int now = q.front();
            q.pop();
            visit[now] = true;
            ac++;
            for(int j = 0 ; j < adj[now].size() ; j++){
                int child = adj[now][j];
                if(!visit[child] && child != b){
                    q.push(child);
                }
            }
        }
        int bc = n-ac;
        if(answer > abs(ac-bc)){
            answer = abs(ac-bc);
        }
    }
    
    return answer;
}

 

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

프로그래머스