개요

프로그래머스 전력망을 둘로 나누기

문제 설명
n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

• 제한사항
  n은 2 이상 100 이하인 자연수입니다.
  wires는 길이가 n-1인 정수형 2차원 배열입니다.
  wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
  1 ≤ v1 < v2 ≤ n 입니다.
  전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.

접근 방식

1. 트리를 두 개의 트리로 나누는 문제이다.
   그래프가 아닌 트리라서 어떤 두 노드 사이를 끊더라도 트리가 두개 생긴다.
   n도 100정도로 작은 수이고 해서 모든 노드를 하나씩 끊어보며
   두 트리의 사이즈를 비교하는 완전탐색 방식으로 짜봤다.

2. DFS방식으로 트리를 순회하며 전체 트리 사이즈를 구하려 했다.
   지금 wire벡터는 각 벡터 안에 연결된 두 노드가 있는 개념이다.
   이렇게 되면 어떤 노드가 서로 연결되어있는지 바로 알기 어렵다.
   따라서 이차원 벡터를 하나 더 만들어준 후, resize함수로 n의 사이즈인
   101로 크기를 할당했다.

   edges.resize(n+1);

3. 그 후, 이차원벡터의 행값을 첫노드, 열값을 두번째 노드로 정하고
   연결한다.

      for(auto elem : wires){
          edges[(elem)[0]].push_back((elem)[1]);
          edges[(elem)[1]].push_back((elem)[0]);
      }

4. 각 노드를 자른 후, 각 트리의 크기를 비교하는 부분은
   CutTree함수에서 담당한다.

   int CutTree(int n, vector<vector<int>>& wires){
      bool visited[101];
      int firstNet=0,secondNet=0,ret=10000;
      for(auto elem : wires){
          fill(visited,visited+101,false);
          visited[(elem)[0]]=true;
          firstNet=DFS(visited,(elem)[1]);
          
          fill(visited,visited+101,false);
          visited[(elem)[1]]=true;
          secondNet=DFS(visited,(elem)[0]);
          
   		ret=min(ret,abs(firstNet-secondNet));
      }
      return ret;
   }

   DFS방식을 이용해야 하니 방문 여부 배열 visited도 선언해준다.

   인자로 받은 wires를 순회하며, 방문 배열 visted를 초기화해준다.
   그 후, 첫번째 DFS함수는 첫번째 노드를 방문 처리해주고,
   두번째 노드를 루트노드로 해서 실행시킨다.

   다시 방문배열 visited를 초기화 해준다.
   두번째 DFS함수는 두번째 노드를 방문 처리해주고,
   이번엔 첫번째 노드를 루트노드로 해서 실행시킨다.

   우리가 원하는 건, 두 전력망의 차이 이므로
   math.h 헤더의 abs 함수를 이용해 두 전력망 차이의 절대값을
   ret과 비교해서 더 작은값을 리턴한다.
   

5. DFS함수는 간단하다.

   int DFS(bool* visited, int curNode){
     visited[curNode]=true;
     //현재 노드에 들어왔으니까 1로 시작
     int Sum=1;
     for(auto elem : edges[curNode]){
         if(visited[elem]) continue;
         Sum+=DFS(visited,elem);
     }
     return Sum;
   }

   인자로 넘어온 visited배열에 현재 단계의 노드 curNode를 방문 체크해준다.
   현재 노드를 포함해야하므로 노드 총합을 나타내는 변수 Sum은 1로 시작한다.
   그 후, 2차원 벡터 edges를 순회하며 curNode와 연결된 노드들로
   DFS함수를 실행 후, 반환값을 Sum변수에 더해준다.
   Sum변수에는 curNode를 루트로하는 서브트리의 노드 갯수가 저장된다.
   

전체코드

#include <string>
#include <vector>
#include<algorithm>
#include<math.h>
using namespace std;
vector<vector<int>> edges;

int DFS(bool* visited, int curNode){
    visited[curNode]=true;
    //현재 노드에 들어왔으니까 1로 시작
    int Sum=1;
    for(auto elem : edges[curNode]){
        if(visited[elem]) continue;
        Sum+=DFS(visited,elem);
    }
    return Sum;
}

int CutTree(int n, vector<vector<int>>& wires){
    bool visited[101];
    int firstNet=0,secondNet=0,ret=10000;
    for(auto elem : wires){
        fill(visited,visited+101,false);
        visited[(elem)[0]]=true;
        firstNet=DFS(visited,(elem)[1]);
        
        fill(visited,visited+101,false);
        visited[(elem)[1]]=true;
        secondNet=DFS(visited,(elem)[0]);
        
        ret=min(ret,abs(firstNet-secondNet));
    }
    return ret;
}

//n이 100개 밖에 안되므로 다 하나씩 끊어봐서 갯수 세는 방식
int solution(int n, vector<vector<int>> wires) {
    int answer = -1;
    edges.resize(n+1);
    for(auto elem : wires){
        edges[(elem)[0]].push_back((elem)[1]);
        edges[(elem)[1]].push_back((elem)[0]);
    }
    answer=CutTree(n,wires);
    return answer;
}

문풀후생

다른사람의 풀이를 보니, 깨달은 바가 있어 적어본다.
DFS를 굳이 두 번할 이유가 없었다!
어차피 전체 노드갯수는 n개이므로 첫번째 트리 갯수만 구한 후,
n에서 빼주면 된다..

따라서 위 코드를 바꿔보면

수정된 코드

#include <string>
#include <vector>
#include<algorithm>
#include<math.h>
using namespace std;
vector<vector<int>> edges;

int DFS(bool* visited, int curNode){
    visited[curNode]=true;
    //현재 노드에 들어왔으니까 1로 시작
    int Sum=1;
    for(auto elem : edges[curNode]){
        if(visited[elem]) continue;
        Sum+=DFS(visited,elem);
    }
    return Sum;
}

int CutTree(int n, vector<vector<int>>& wires){
    bool visited[101];
    int firstNet=0,secondNet=0,ret=10000;
    for(auto elem : wires){
        fill(visited,visited+101,false);
        visited[(elem)[0]]=true;
        firstNet=DFS(visited,(elem)[1]);
        secondNet=n-firstNet;
        
        ret=min(ret,abs(firstNet-secondNet));
    }
    return ret;
}

//n이 100개 밖에 안되므로 다 하나씩 끊어봐서 갯수 세는 방식
int solution(int n, vector<vector<int>> wires) {
    int answer = -1;
    edges.resize(n+1);
    for(auto elem : wires){
        edges[(elem)[0]].push_back((elem)[1]);
        edges[(elem)[1]].push_back((elem)[0]);
    }
    answer=CutTree(n,wires);
    return answer;
}

이런식으로 n- firstNet해줘도 된다.