[프로그래머스] Level 2. 전력망을 둘로 나누기

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

프로그래머스

 

 

문제 접근 방법

1. 간선의 연결 정보를 저장한다.
   간선 정보를 저장하기 위해 2차원 배열(인접 리스트)을 선언한다. 예를 들어 [1, 3]이라는 간선이 있으면, 1번 노드와 3번 노드 양쪽에 각각 연결 정보를 추가한다. 이렇게 하면 양방향 그래프로 간선을 쉽게 관리할 수 있다.
2. 하나씩 간선을 제거하면서 두 트리의 개수 차이를 계산한다.
   모든 간선을 하나씩 제거해 보고, 그때 두 개의 트리로 나뉘게 된다. 이때 0번 노드에서 시작해서 BFS로 탐색하며 한쪽 트리의 노드 개수를 구한다. 전체 노드 개수에서 이 값을 빼면 다른 한쪽 트리의 개수가 된다. 이렇게 해서 두 트리의 개수 차이를 구한다.
3. 가장 작은 차이를 찾는다.
   모든 간선에 대해 위 과정을 반복하고, 트리 개수 차이가 가장 작은 경우를 정답으로 반환한다.

구현 시 주의할 점

• 방문 처리: 중복 방문을 방지하기 위해 visited 배열을 사용한다.
• 간선 제거 처리: 실제로 간선을 제거하는 대신, getDiff 함수에 제거할 간선 정보를 넘겨주고, BFS 탐색 시 해당 간선을 건너뛰도록 처리한다.

 

#include <string>
#include <vector>
#include <climits>
#include <queue>
#include <iostream>
using namespace std;

vector<vector<int>> w;

//a-b로 이동하는 간선을 제거했을 때 두 트리의 개수 차이를 반환.
int getDiff(int a, int b){
    
    vector<bool> visited(w.size(),false);
    queue<int> q;
    int cnt = 1;
    visited[0] = true;
    q.push(0);
    
    while(!q.empty()){
        int crr = q.front(); //현재검사노드. 
        q.pop();
        for(int i =0; i<w[crr].size(); i++){ //연결된 모든 선을 검사하여 cnt ++ 해준다.
            int n = w[crr][i];
            if((crr == a && n == b) || (crr == b && n == a)) continue; //제거된 간선. 
            if(!visited[n]){
                cnt ++;  
                q.push(n);
            } 
            visited[n] = true;
        }
    }
    
    int others = w.size()-cnt;
    return cnt < others ? others - cnt : cnt  - others;

}


int solution(int n, vector<vector<int>> wires) {
    
    int answer = INT_MAX;
    w.resize(n);
    
    //연결정보 세팅. 양방향 이동가능.
    for(int i=0 ; i<wires.size(); i++){
        int a= wires[i][0]-1; int b= wires[i][1]-1;
        w[a].push_back(b);
        w[b].push_back(a);
    }
    
    
    //각 간선제거 횟수구함
    for(int i=0; i<wires.size(); i++){
        answer = min(answer, getDiff(wires[i][0]-1, wires[i][1]-1));
    }
    
    
    return answer;
}

핵심 포인트

1. 간선 제거는 실제로 하지 않고, 탐색 시 무시한다.
2. BFS로 연결된 노드 개수를 정확히 세어야 한다.
3. 모든 간선에 대해 반복하면서 최소 차이를 찾는다.