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

 

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

 

https://school.programmers.co.kr/learn/courses/30/lessons/86971

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

---

 

해결전략

 

완전탐색

 

---

 

DFS 코드

 

#include <cmath>
#include <vector>
using namespace std;
 
vector<vector<int>> adj; // 각 노드의 인접 노드를 저장
vector<int> ch; // 각 노드가 속한 서브트리의 크기를 저장
 
// DFS 함수. 현재 노드와 이전에 방문한 노드를 인자로 받는다.
void DFS(int curr, int prev = -1)
{
    // 현재 노드를 방문했으므로 ch[curr]을 1로 설정
    ch[curr] = 1;
 
    // 현재 노드의 모든 인접노드에 대해 반복
    for (int i = 0; i < adj[curr].size(); i++)
    {
        int next = adj[curr][i];
 
        // 이전에 방문한 노드가 아니라면
        if (next != prev) {
            // 해당 인접노드에 대해 DFS를 수행하고,
            DFS(next, curr);
            // 해당 인접노드가 속한 서브트리의 크기(ch[next])를 현재노트의 서브트리 크기(ch[curr])에 추가합니다.
            ch[curr] += ch[next];
        }
    }
}
 
int solution(int n, vector<vector<int>> wires) {
    int answer = n;
 
    // 벡터들을 초기화합니다. 
    adj.resize(n+1);
    ch.resize(n+1);
 
   // 모든 전선 정보에 대해 반복하며
   for (int i = 0; i < wires.size(); i++)
   {
       int node1 = wires[i][0];
       int node2 = wires[i][1];
 
       // 양방향 그래프이므로 각각 반대쪽 정점을 추가
       adj[node1].push_back(node2);
       adj[node2].push_back(node1);
   }
 
   // 첫 번째 송전탑에서 시작하는 DFS를 수행하여 모든 송전탑이 속한 서브트리의 크기를 계산
   DFS(1);
 
   for (int i = 2; i <= n; ++i)
      // 전체 송전탑 개수에서 특정 송전탑이 포함된 서브트리의 크기(ch[i]) * 2 값을 뺀 값과 기존 answer 값 중 작은 값을 찾아 answer 에 업데이트 
      answer = min(answer, abs(n - 2 * ch[i]));
 
   // 최종적으로 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 반환
   return answer;
}

 

 

---

 

BFS 코드

 

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int solution(int n, vector<vector<int>> wires) {
    int answer = n; // 초기값은 전체 송전탑의 개수로 설정
    vector<vector<int>> adj(n+1); // 각 노드의 인접 노드를 저장하는 인접 리스트를 선언
 
    for (auto& wire : wires) { // 모든 전선 정보에 대해 반복
        adj[wire[0]].push_back(wire[1]); // 양방향 그래프이므로 각각 반대쪽 정점을 추가
        adj[wire[1]].push_back(wire[0]);
    }
 
    for (auto& cutWire : wires) // 모든 전선에 대해 하나씩 끊어보며 반복
    { 
        vector<bool> visited(n+1, false); // 방문 여부를 저장하는 벡터를 선언하고 초기화
        queue<int> q;  // BFS를 위한 큐를 선언
 
        visited[cutWire[0]] = true;  // 첫 번째 네트워크 생성을 위해 첫 번째 송전탑을 방문 처리하고 큐에 넣는다.
        q.push(cutWire[0]);
 
        int count = 0;  // 첫 번째 네트워크의 송전탑 개수를 저장할 변수
        
        while (!q.empty()) // BFS 알고리즘 실행
        {  
            int current = q.front();
            q.pop();
            count++;   // 현재 송전탑이 첫 번째 네트워크에 포함되므로 카운트 증가
 
            for (int next : adj[current]) // 현재 송전탑과 연결된 모든 송전탑에 대해 반복
            {   
             	// 만약 다음 탐색할 노드와 현재 노드가 끊긴 전선이라면 건너뛴다.
                if ((current == cutWire[0] && next == cutWire[1]) || 
                    (current == cutWire[1] && next == cutWire[0])) continue; 
                
                // 아직 방문하지 않은 탐색 가능한 다음 노드라면
                if (!visited[next]) { 
                    visited[next] = true;
                    q.push(next);
                }
            }
        }
 
       /* 간선 한 개가 제거된 상태에서 BFS로 찾아낼 수 있는 최대 노드의 개수(첫 번째 네트워크)를 구했으므로, 
          전체 노드 개수에서 이를 빼면 나머지 노드의 개수(두 번째 네트워크)를 알 수 있다. 
          이렇게 구한 두 네트워크의 크기 차이의 절대값을 계산하고, 그 중 최소값을 찾아서 answer에 저장한다. */
        answer = min(answer, abs(n - 2 * count)); 
    }
 
    return answer; // 최종적으로 구한 최소 차이 값을 반환
}

 

 

 

 

---