알고리즘 문제풀이
[프로그래머스] 전력망을 둘로 나누기 (C++)
SiO2whocode
2024. 11. 4. 15:33
728x90
완전탐색
N개의 송전탑이 하나의 트리를 구성하며 연결되어 있는데, 간선 하나를 잘라서 두개의 트리로 분리할 때
이 두개의 트리의 송전탑 개수 차가 최소가 되는 그 최소값을 반환하는 문제
두 송전탑을 잇는 간선이 이렇게 wires 라는 배열로 주어짐 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]
간선은 한개씩만 주어지지만 양방향 간선임
접근방법
완전탐색인 만큼..모든 간선을 잘라보면서 두 그래프의 노드 수 차이를 구해보면 된다.
우선 인접행렬을 만들어서 사용했고,
하나의 간선 (1,3) 을 자르면, 1로 시작해서 갈 수 있는 노드들을 모두 센다 큐를 하나 만들어서 bfs처럼 풀었음
근데, 노드를 방문할 때 3이면 방문하지 않음 => 3으로부터 뻣어갈 수 있는 노드들은 방문하지 않음 = 3과의 간선이 끊어졌을 때 1을 루트노드로 하는 트리의 노드 수(ac)를 알게 됨
-> N에서 ac를 빼면 bc(3을 루트노드로 하는 트리의 노드 수)가 되므로
abs(ac-bc = 2ac-n)가 최소가 되는 경우를 구하면 된다.
소스코드
#include <string>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
int solution(int n, vector<vector<int>> wires) {
int answer = n;
vector<vector<int>> adj(n+1);
for(int i = 0 ; i < wires.size() ; i++){
int a = wires[i][0];
int b = wires[i][1];
adj[a].push_back(b);
adj[b].push_back(a);
}
for(int i = 0 ; i < wires.size() ; i++){
int a = wires[i][0];
int b = wires[i][1];
int ac = 0; // 각 트리의 노드수
vector<bool> visit(n+1, false);
queue<int> q;
q.push(a);
while(!q.empty()){
int now = q.front();
q.pop();
visit[now] = true;
ac++;
for(int j = 0 ; j < adj[now].size() ; j++){
int child = adj[now][j];
if(!visit[child] && child != b){
q.push(child);
}
}
}
int bc = n-ac;
if(answer > abs(ac-bc)){
answer = abs(ac-bc);
}
}
return answer;
}
https://school.programmers.co.kr/learn/courses/30/lessons/86971
728x90