-
[프로그래머스] 전력망을 둘로 나누기 c++Coding Test/programmers 2022. 9. 30. 13:20728x90
문제 설명
n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.
송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.
제한 사항
- n은 2 이상 100 이하인 자연수입니다.
- wires는 길이가 n-1인 정수형 2차원 배열입니다.
- wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
- 1 ≤ v1 < v2 ≤ n 입니다.
- 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.
입출력 예
n wires result 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 4 [[1,2],[2,3],[3,4]] 0 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 풀이
1. 송전탑 i번에 연결되어 있는 모든 송전탑 번호를 벡터m에 저장한다. (벡터 m은 2차원 벡터이다.)
2. 연결되어 있는 송전탑 정보인 wires에 총 몇개의 전선이 연결되어 있는지 검사한다.
( wires[0][] , wires[1][], .... , wires[n-1][])
wires[0][] ~ wires[n-1][] : 8개의 전선으로 연결되어 있다.
wires[1][] ~ wires[n-1][] : 8개의 전선으로 연결되어 있다. → wires[0][] 연결을 끊겠다는 뜻이다.
wires[2][] ~ wires[n-1][] : 6개의 전선으로 연결되어 있다. → wires[0][], wire[1][] 연결을 끊겠단는 뜻이다.
...
3. 2번을 bfs로 검사한다. 연결되어 있지 않으면, 어디에 연결되어 있는지 검사한다.
4. 가장 차이가 적은 값을 저장한다.
#include <string> #include <vector> #include <climits> using namespace std; vector<int> m[200]; int bfs(int togo, int now, int cnt){ for(int i = 0; i < m[now].size(); i++){ if(m[now][i] != togo){ cnt = bfs(now, m[now][i] , cnt + 1); } } return cnt; } int solution(int n, vector<vector<int>> wires) { for(const auto& it : wires){ m[it[0]].push_back(it[1]); m[it[1]].push_back(it[0]); } int answer = INT8_MAX; for(const auto& it : wires){ int sum = bfs(it[0], it[1], 1); int comp = n - (sum * 2); answer = min(answer, abs(comp)); } return answer; }
다른 풀이
#include <string> #include <vector> #include <functional> #include <climits> using namespace std; int solution(int n, vector<vector<int>> wires) { vector<vector<int>> graph(n+1); for(const auto& it : wires){ graph[it[0]].push_back(it[1]); graph[it[1]].push_back(it[0]); } int answer = INT8_MAX; vector<int> siz(n+1); function<void(int, int)> dfs = [&](int cur, int prev) -> void{ siz[cur] = 1; for(int nxt : graph[cur]){ if(nxt == prev){ continue; } dfs(nxt, cur); siz[cur] += siz[nxt]; } }; dfs(1, -1); 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; }
function 확인하기!
728x90'Coding Test > programmers' 카테고리의 다른 글
[프로그래머스] 할인 행사 c++ (2) 2022.10.11 [프로그래머스] 빛의 경로 사이클 c++ (2) 2022.10.04 [프로그래머스] n^2 배열 자르기 c++ (0) 2022.09.29 [프로그래머스] 교점에 별 만들기 c++ (2) 2022.09.29 [프로그래머스] 피로도 c++ (0) 2022.09.28