[Algorithm] 프로그래머스 전력망을 둘로 나누기 - C++, DFS

프로그래머스

#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)를 구해도 되었을 것 같네요)