Algorithm/dfs
프로그래머스 전력망을 둘로 나누기 c++ // int dfs 자식수세기
Mini_96
2023. 10. 2. 14:10
https://school.programmers.co.kr/learn/courses/30/lessons/86971
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
1. int dfs 자식수세기
지역변수로 ret=1
ret+=dfs(next)
return ret 하면된다.
int dfs(int node){
visited[node]=1;
int ret=1;
for(int next=0;next<104;++next){
if(adj[node][next]==0) continue; //연결이아니면 pass
if(adj[next][node]==0) continue; //연결이아니면 pass
if(visited[next]) continue;
ret+=dfs(next);
}
return ret;
}
전체코드
#include <bits/stdc++.h>
using namespace std;
int visited[104];
int adj[104][104];
int dfs(int node){
visited[node]=1;
int ret=1;
for(int next=0;next<104;++next){
if(adj[node][next]==0) continue; //연결이아니면 pass
if(adj[next][node]==0) continue; //연결이아니면 pass
if(visited[next]) continue;
ret+=dfs(next);
}
return ret;
}
int solution(int n, vector<vector<int>> wires) {
int answer = 987654321;
//1. 1개씩 연결끊기
//2. dfs 돌면서 연결된 노드세기
//3. 최대값 차이 갱신
//4. 시간복잡도 : n(for)*n(for)*n(dfs)==1000000 가능
//연결해주기
for(auto v : wires){
adj[v[0]][v[1]]=1;
adj[v[1]][v[0]]=1;
}
for(auto v : wires){
//1. visit 초기화
fill(visited,visited+104,0);
adj[v[0]][v[1]]=0;
adj[v[1]][v[0]]=0;
vector<int> temp;
for(int i=1;i<=n;++i){
if(visited[i]) continue;
temp.push_back(dfs(i));
}
// for(auto i : temp){
// cout<<i<<" ";
// }
// cout<<"\n";
answer=min(answer,abs(temp[0]-temp[1]));
//탐색끝나면 다시연결해주기
adj[v[0]][v[1]]=1;
adj[v[1]][v[0]]=1;
}
return answer;
}