프로그래머스 : 완전탐색 - 전력망을 둘로 나누

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

프로그래머스

 

완전탐색이고 그래프니까, BFS또는 DFS였다!

근데,, DFS로 풀었어야 했던것같은데 난 BFS로 풀었다..ㅎㅎ..;;;

생각해보면, "완전탐색" 일때는 DFS나 BFS나 비슷하지 않으려나??

최소경로 같은 문제면, DFS로 했을 때 중간멈춤이 안되어서 (완전탐색 강제) BFS를 써야했지만

어짜피 완전탐색이면 DFS나 BFS나 모든 노드에 방문해봐야 하는건 같을텐데... 흠...

 

---

풀이 자체는 간단했다.

wire가 배열로 주어지니가 하나씩 끊어서 트리 노드개수의 차를 전부 확인해 보면 됐다!

 

#include <string>
#include <vector>
#include <climits>
#include <queue>
#include <iostream>

using namespace std;

int find_seed(vector<vector<int>> wires){
    for(int i = 0; i<wires.size(); i++){
        for(int j = 0; j<wires.size(); j++){
            if(wires[i][j] == 1){
                return i;
            }
        }
    }
    return -1;
}

int tree_count_sub(vector<vector<int>> wires){
    
    
    // 첫번째 트리 개수 찾기
    int count1 = 1;
    queue<int> que;
    que.push(0);
    while(!que.empty()){
        int node = que.front();
        que.pop();
        for(int i = 0; i<wires.size(); i++){
            if(wires[node][i] == 1){
                // 연결된곳을 찾은것
                wires[node][i] = 0;
                wires[i][node] = 0;
                que.push(i);
                count1++;
            }
        }
        
    }
    
    //cout << "1 : "<<count1<<endl;
    
    // 두번째 트리 개수 찾기
    int count2 = 1;
    queue<int> que2;
    int n = find_seed(wires);
    que2.push(n);
    if(n == -1){
        return INT_MAX;
    }
    
    while(!que2.empty()){
        int node = que2.front();
        que2.pop();
        for(int i = 0; i<wires.size(); i++){
            if(wires[node][i] == 1){
                // 연결된곳을 찾은것
                wires[node][i] = 0;
                wires[i][node] = 0;
                que2.push(i);
                count2++;
            }
        }
        
    }
    
    return abs(count1 - count2);
}

int solution(int n, vector<vector<int>> wires) {
    int answer = INT_MAX;
    
    vector<vector<int>> trees(n, vector<int>(n, 0));
    
    for(int i = 0; i<wires.size(); i++){
        trees[wires[i][0]-1][wires[i][1]-1] = 1;
        trees[wires[i][1]-1][wires[i][0]-1] = 1;
    }
    
    for(int i = 0; i<wires.size(); i++){
        vector<vector<int>> test = trees;
        test[wires[i][0]-1][wires[i][1]-1] = 0;
        test[wires[i][1]-1][wires[i][0]-1] = 0;
        // 끊기
        
        answer = min(answer, tree_count_sub(test));
        
    }
    
    return answer;
}

 

---

그리고 다른사람 풀이를 확인하던 도중,..

tree_count_sub 함수 내에서 두번째 트리의 개수를 찾는 부분이 필요 없다는걸 알게되었다!ㅋㅋㅋㅋㅋㅋ

아 진짜 간단한거였는데... 멍청했다.

전체 송전탑의 개수는 주어져있고, 첫번째 트리의 개수만 구하면, 두번째 트리의 개수는 n - count1로 고정된다..ㅎㅎ

 

#include <string>
#include <vector>
#include <climits>
#include <queue>
#include <iostream>

using namespace std;


int tree_count_sub(vector<vector<int>> wires, int n){
    
    
    // 첫번째 트리 개수 찾기
    int count1 = 1;
    queue<int> que;
    que.push(0);
    while(!que.empty()){
        int node = que.front();
        que.pop();
        for(int i = 0; i<wires.size(); i++){
            if(wires[node][i] == 1){
                // 연결된곳을 찾은것
                wires[node][i] = 0;
                wires[i][node] = 0;
                que.push(i);
                count1++;
            }
        }
        
    }
    
    //cout << "1 : "<<count1<<endl;
    
    // 두번째 트리 개수 찾기
    int count2 = n - count1;
    
    
    return abs(count1 - count2);
}

int solution(int n, vector<vector<int>> wires) {
    int answer = INT_MAX;
    
    vector<vector<int>> trees(n, vector<int>(n, 0));
    
    for(int i = 0; i<wires.size(); i++){
        trees[wires[i][0]-1][wires[i][1]-1] = 1;
        trees[wires[i][1]-1][wires[i][0]-1] = 1;
    }
    
    for(int i = 0; i<wires.size(); i++){
        vector<vector<int>> test = trees;
        test[wires[i][0]-1][wires[i][1]-1] = 0;
        test[wires[i][1]-1][wires[i][0]-1] = 0;
        // 끊기
        
        answer = min(answer, tree_count_sub(test, n));
        
    }
    
    return answer;
}

이렇게 수정해줄 수 있었다.