쾌락없는 책임 (공부)/알고리즘 문제풀이
[Algorithm] 프로그래머스 전력망을 둘로 나누기 - C++, DFS
허스크
2022. 8. 30. 00:31
반응형
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
#include <string>
#include <vector>
#include <cstring>
using namespace std;
const int MAX = 101;
bool edges[MAX][MAX];
bool visit[MAX];
void ClearVisit(int _totalNum)
{
for(int i = 1; i <= _totalNum; i++)
{
visit[i] = false;
}
}
int GetConnectedCityNum(int _start, int _totalNum)
{
if(visit[_start]) return 0;
int cityCount = 1;
visit[_start] = true;
for(int i = 1; i <= _totalNum; i++)
{
if(!edges[_start][i]) continue;
cityCount += GetConnectedCityNum(i, _totalNum);
}
return cityCount;
}
int solution(int n, vector<vector<int>> wires) {
int answer = n + 1;
for(int i = 0; i < wires.size(); i++)
{
const int from = wires[i][0];
const int to = wires[i][1];
edges[from][to] = true;
edges[to][from] = true;
}
for(int i = 0; i < wires.size(); i++)
{
ClearVisit(n);
const int from = wires[i][0];
const int to = wires[i][1];
edges[from][to] = false;
edges[to][from] = false;
// from city's number
int firstSide = GetConnectedCityNum(from, n);
if(visit[to]) continue; // if still one tree
// to city's number
int otherSide = n - firstSide;
// calculate the difference
answer = min(answer, abs(firstSide - otherSide));
edges[from][to] = true;
edges[to][from] = true;
}
return answer;
}
DFS 감을 잡기 좋은 문제였습니다. 일단 주어진 벡터에서 edges[][]를 뽑아낸 뒤 DFS를 이용한 함수를 통해 "해당 지점에서 연결된 노드가 몇개"인지를 구해줍니다. 다시보니 이걸 준비하는게 BFS여도 문제 없을 것 같긴 하네요.
이제 함수들이 준비되었으니 루프문을 통해서 모든 연결을 해제하는 식으로 탐색을 합니다. n이 100이라 충분히 가능한 작업량입니다. 만일 구하고 나서 끊은 연결의 다른 쪽이 방문했다면 이는 아직 트리가 완전 분리되지 않았다는 뜻이니 더 볼 필요 없이 continue를 하면 되고 만일 아니라면 그냥 전체 수에서 다른 트리의 수를 빼면 남은 트리의 노드 수가 나오게 됩니다. 때문에 함수를 한번 더 돌릴 필요는 없죠.
(+ 추가로 생각해보니 otherSide를 굳이 추가하지 말고 abs(2firstSide - n)를 구해도 되었을 것 같네요)
반응형