프로그래머스 위클리 챌린지9주차 전력망을 둘로 나누기

1. 문제 링크

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

코딩테스트 연습 - 9주차

 

2.  풀이

 

정점의 개수가 n개인 트리에서 간선 하나를 제거했을 때 2개의 트리로 분리되는데, 이때 분리된 2개의 트리의 정점 수의 차이의 최솟값을 구하는 문제이다.

 

단순히 모든 간선을 한번씩 제거해 가면서, 각각의 경우에 BFS로 2개의 분리된 트리의 정점 수를 카운트하는 방식으로 해결했다.

 

위 방식은 O(n^2)인데, n의 최대가 100이기 때문에 가능했다.

 

//트리 => 인접리스트로 그래프 표현

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

using namespace std;

const int MAX = 200000000;
vector<int> graph[101];
bool visited[101];

void initGraph(const vector<vector<int>>& wires){
    for(vector<int> ele: wires){
        graph[ele[0]].push_back(ele[1]);
        graph[ele[1]].push_back(ele[0]);
    }
}

void initVisited(const int& n){
    for(int i = 1;i<=n;i++)
        visited[i] = false;
}

int BFS(const vector<int>& removedWire, const int& start){
    //start에서 출발해서 BFS탐색한 후 총 탐색한 노드 갯수 리턴
    queue<int> q;
    q.push(start);
    visited[start] = true;
    int res = 1;

    while(!q.empty()){
        int currentNode = q.front(); q.pop();
        for(int nextNode : graph[currentNode]){
            if(visited[nextNode])
                continue;
            if(removedWire[0] == currentNode && removedWire[1] == nextNode)
                continue;
            if(removedWire[1] == currentNode && removedWire[0] == nextNode)
                continue;
            
            q.push(nextNode);
            visited[nextNode] = true;
            res++;
        }
    }
    
    return res;
}

int Cal(const vector<int>& removedWire, const int& n){
    //removedWire가 제거되었을때 절댓값 차이를 계산 후 ans를 최소로 업데이트
    initVisited(n);
    vector<int> tmp;
    int cnt = 0;
    for(int node = 1;node<=n;node++){
        if(visited[node])
            continue;
        tmp.push_back(BFS(removedWire, node));
        cnt++;
        if(cnt == 2)
            break;
    }
    
    return (tmp[0] > tmp[1])? (tmp[0] - tmp[1]):(tmp[1] - tmp[0]);
}

//n:        송전탑 수(노드 수)                                  2~100
//wires:    전선 정보 wires(간선) => 무방향 & 가중치 없음         n-1개(트리)
int solution(int n, vector<vector<int>> wires) {
    initGraph(wires);
    int ans = MAX;
    for(vector<int> ele: wires){
        int tmp = Cal(ele,n);
        ans = ans < tmp ? ans : tmp;
    }
    return ans;
}