프로그래머스 : 전력망을 둘로 나누기

문제

풀이

문제의 입력으로 송전탑의 개수(n)와 송전탑들이 이어진 전선들의 정보(wires)가 주어진다

그래서 송전탑들은 트리의 형태로 연결됨을 보장하는데 사이클이 없음을 확인할 수 있다

문제에서 요구하는 것은 전선들 wires 중에서 하나를 잘라 두 개의 전력망으로 분할시킬건데 두 전력망에 있는 송전탑의 개수의 차이의 최소를 구해야 한다

입력 크기가 충분히 작기 때문에 완전 탐색이 가능한 문제이다

우선 wires를 바탕으로 인접 그래프 adj를 초기화했다. adj[i].push_back(j)는 i번째 송신탑에서 j번째 송신탑으로 네트워크가 이어져 있음을 의미함

그 다음 wires를 반복문으로 돌면서 BFS를 통해 1번째 송신탑에서 출발해서 이어져 있는 송신탑들을 방문하며 visited 배열을 1로 초기화한다

BFS를 돌면서 현재 wires[i]의 네트워크를 안 쓰는 것이기 때문에 다음 송신탑을 큐에 추가할 때 조건으로 현재 탑 또는 다음 탑이 wires[i]에 포함되면 continue 하는 조건을 넣어 뒀다

BFS가 끝나면 visited 배열들이 0 또는 1로 초기화되어 있는데 이는 두 개의 전력망으로 분리된 것을 의미한다

그래서 0과 1의 개수의 차이값으로 정답을 갱신했다

코드

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

int solution(int n, vector<vector<int>> wires) {
    int answer = 987654321;
    
    vector<vector<int>> adj(n + 1, vector<int>());
    
    for(int i = 0; i < wires.size(); i++)
    {
        adj[wires[i][0]].push_back(wires[i][1]);
        adj[wires[i][1]].push_back(wires[i][0]);
    }
    
    for(int i = 0; i < wires.size(); i++)
    {
        vector<int> visited(n + 1, 0);
        
        queue<int> q;
        q.push(1);
        
        while(!q.empty())
        {
            int top = q.front();
            q.pop();
            visited[top] = 1;
            
            for(int nextTop : adj[top])
            {
                if(visited[nextTop] || (top == wires[i][0] && nextTop == wires[i][1]) || (top == wires[i][1] && nextTop == wires[i][0])) continue;
                
                q.push(nextTop);
            }
        }
        
        int c1 = 0, c2 = 0;
        
        for(int j = 1; j <= n; j++)
        {
            if(visited[j] == 1) c1++;
            else c2++;
        }
        
        answer = min(answer, abs(c1 - c2));
    }
    
    
    return answer;
}