문제 풀이/프로그래머스
프로그래머스 - 전력망을 둘로 나누기
JJJaewon
2023. 3. 12. 18:03
반응형
코딩테스트 고득점 Kit 완전탐색 Level 2 전력망을 둘로 나누기 문제이다. 나는 처음에 이 문제를 유니온 파인드를 이용해서 풀려고 했지만 구현이 쉽지 않았다. 입력 n 이 100으로 아주 작고, 트리로 주어지므로 시간 복잡도가 100 * 100 * 100 정도로 아주 작다. 따라서 이 문제는 완전 탐색, dfs를 이용해서 풀었다. dfs가 끝날 때마다 temp++를 실행함으로써 dfs가 최종 종료했을 때 몇개의 노드가 연결되어있는지 알수 있도록 구현했다.
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int ans = INT32_MAX;
vector<vector<int>> adj;
vector<bool> visited;
vector<int> result;
int temp;
void dfs(int n, int start)
{
visited[start] = true;
for (int i = 0; i < adj[start].size(); i++)
{
int next = adj[start][i];
if (!visited[next])
{
dfs(n, next);
}
}
temp++;
}
void func(int n, vector<vector<int>>& wires)
{
for (int i = 0; i < wires.size(); i++)
{
adj = vector<vector<int>>(n + 1);
visited = vector<bool>(n + 1, false);
result = vector<int>();
for (int j = 0; j < wires.size(); j++)
{
if (i == j)
{
continue;
}
int a = wires[j][0];
int b = wires[j][1];
adj[a].push_back(b);
adj[b].push_back(a);
}
for (int i = 1; i <= n; i++)
{
if (!visited[i])
{
temp = 0;
dfs(n, i);
result.push_back(temp);
}
}
ans = min(ans, abs(result[0] - result[1]));
}
}
int solution(int n, vector<vector<int>> wires) {
int answer = -1;
func(n, wires);
answer = ans;
return answer;
}
반응형