코딩테스트 : 전력망을 둘로 나누기

해당 문제는 Wire 한개를 끊었을 때 연결되어 있는 두 개의 그룹의 송전탑 개수를 구하는 문제로 두개의 송전탑은 최대 한개의 Wire로 연결되어 있다는 점을 이용해서 문제를 풀었다.

이러한 특징을 이용한다면 [3,4] 와이어를 끊는다면 나누어지는 두 그룹엔 3과 4가 각각 한개씩 밖에 존재하지 않게 된다. 이후 wire에 3이 있으면 1번 그룹, 4가 있으면 2번 그룹으로 구분해서 그룹 내 송전탑의 갯수를 구하면 된다.

송전탑은 번호마다 한개씩 있기에 set을 이용해 중복되는 원소 없이 그룹에 저장한다.

구현 방법

#include <string>
#include <vector>
#include <set>
#include <climits>
#include <algorithm>

using namespace std;

int solution(int n, vector<vector<int>> wires) {
		//두 그룹의 송전탑 차 중 최소값(최소 값 구하는 문제이기에 int 중 가장 큰 INT_MAX 사용)
    int min = INT_MAX;
    
    //wires를 돌며 해당하는 전선을 한개씩 끊어서 min 값을 구한다.
    for(int i = 0; i < wires.size(); i++)
    {
		    //a그룹의 송전탑
        set<int> a;
        //b그룹의 송전탑
        set<int> b;
        
        //끊은 전선을 기준으로 a,b 그룹 생성
        a.insert(wires[i][0]);
        b.insert(wires[i][1]);
        
        //a,b 그룹에 송전탑 갯수 합이 n이면 전력망을 다 나눈것
        while(a.size() + b.size() != n)
        {
            for(int j = 0; j < wires.size(); j++)
            {
                if(i != j)
                {
										//선택한 와이어가 a,b중 어디에 연결되어 있는지
                    auto a0 = a.find(wires[j][0]);
                    auto a1 = a.find(wires[j][1]);
                    //a에 연결되어 있다면
                    if(a0 != a.end() || a1 != a.end())
                    {
		                    //송전탑을 a그룹에 넣기
		                    //중복은 자동으로 삭제
                        a.insert(wires[j][0]);
                        a.insert(wires[j][1]);
                    }

                    auto b0 = b.find(wires[j][0]);
                    auto b1 = b.find(wires[j][1]);
                    if(b0 != b.end() || b1 != b.end())
                    {
                        b.insert(wires[j][0]);
                        b.insert(wires[j][1]);
                    }
                }
            }
        }
        
        //a와 b의 송전탑 개수 차이
        int result = a.size() - b.size();
        //차이를 절대값으로 변경
        result = result > 0 ? result : result * -1;
        //min과 비교하며 최소값 찾기
        min = result < min ? result : min;
    }
    
    return min;
}

프로그래머스 베스트 답안 설명

#include <bits/stdc++.h>

using namespace std;

int solution(int n, vector<vector<int>> wires) {
    //0번 인덱스는 사용하지 않기에 N + 1
    vector<vector<int>> graph(n + 1);
    //wires 전체를 돌며 각 송전탑에 연결되어 있는 송전탑 정보 저장
    for(int i = 0; i < (int)wires.size(); i++) {
        int u = wires[i][0];
        int v = wires[i][1];
        //u,v는 서로 연결되어 있으니 서로에게 서로를 추가
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    //n + 1 만큼 벡터 생성
    vector<int> siz(n + 1);
    
    //람다함수를 만든 뒤 function을 이용해 dfs에 저장
    //dfs는 반환 값이 void인 int,int를 매개변수로 받는 함수이며 현재 스코프에서 모든 값을 참조(&)로 가져온다.
    function<void(int, int)> dfs = [&](int cur, int prev)  -> void {
        //현재 송전탑을 포함하므로 1로 초기화
        siz[cur] = 1;
        //cur 송전탑과 연결된 송전탑 정보 한개씩 불러옴
        for(int nxt : graph[cur]) {
            //이전 송전탑은 다시 계산하지 않는다.
            if(nxt == prev) continue;
            //다음 송전탑에 대해 dfs 호출
            dfs(nxt, cur);
            //크기 갱신
            siz[cur] += siz[nxt];
        }
    };
    
    //1번 송전탑부터 DFS 수행
    dfs(1, -1);
    int answer = INT_MAX;
    //모든 송전탑에 중 최솟값 구하기
    for(int i = 1; i <= n; i++) {
        for(int j : graph[i]) {
            int l = siz[j];
            int r = n - siz[j];
            answer = min(answer, abs(l - r));
        }
    }
    return answer;
}

 

테스트 케이스

n = 9
wires = [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]
return = 3

n = 4
wires = [[1,2],[2,3],[3,4]]
return = 0


n = 7
wires = [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]]
return = 1


n = 5
wires = [[1,2],[2,3],[3,4],[4,5]]
return = 1


n = 6
wires = [[1,2],[2,3],[3,4],[4,5],[5,6]]
return = 0


n = 8
wires = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7],[6,8]]
return = 0