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

11/10

그러면 이차원 vector로 만든 다음에 제일 연결이 많은 애 기준으로 연결 잘라가면서 비교해보는 방법을 써야할듯

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

void dfs(vector<vector<int>>&link, vector<bool>&visit, int ml, int m_l, int num, int &ans){
    visit[ml] = 1;
    ans++;

    for(int x = 0; x < link[ml].size(); x++){
        if(ml == m_l && link[ml][x] == num) continue;
        if(!visit[link[ml][x]]) {
            dfs(link, visit, link[ml][x], m_l, num, ans);
        }
    }
} // 완전탐색

int solution(int n, vector<vector<int>> wires) {
    
    vector<vector<int>>link(n+1);
    for(auto x : wires){
        link[x[0]].push_back(x[1]);
        link[x[1]].push_back(x[0]);
    } //보기 편하게 바꾸기

    int max_link = 0;
    for(int i = 1; i<=n; ++i){
        if(max_link < link[i].size()) max_link = i;
    }

    int answer = 10000;
    for(auto num : link[max_link]){
        vector<bool>visit(n+1, 0);
        int ans = 0;
        dfs(link, visit, max_link, max_link, num, ans);
        answer = min(answer, abs(ans*2-n));
        //cout << num << " ** " << ans << " ** " << abs(ans*2-n) << "\n";
    }

    return answer;
}

이렇게 했을 떄 연습문제는 성공이었는데... 결과는,,,,?!?!?!

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 테스트 케이스 3개만 운좋게 맞았나보다..... 

뭐가 문제일까??

 

11/12.....

기존에 내가 한 방법은 그냥 제일 연결 많은 애꺼를 끊어내는건데

이게 연결이 조금이여도 거기 뒤에 딸린 애들의 개수가 많을 수도 있으니까

이런 넉낌으로다가.............

모든 노드를 다 끊는걸로 바꿔보자....

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

void dfs(vector<vector<int>>&link, vector<bool>&visit, int ml, int m_l, int num, int &ans){
    visit[ml] = 1;
    ans++;

    for(int x = 0; x < link[ml].size(); x++){
        if(ml == m_l && link[ml][x] == num) continue;
        if(!visit[link[ml][x]]) {
            dfs(link, visit, link[ml][x], m_l, num, ans);
        }
    }
} // 완전탐색

int solution(int n, vector<vector<int>> wires) {
    
    vector<vector<int>>link(n+1);
    for(auto x : wires){
        link[x[0]].push_back(x[1]);
        link[x[1]].push_back(x[0]);
    } //보기 편하게 바꾸기

    int answer = 10000;
    for(auto x: wires){
        vector<bool>visit(n+1, 0);
        int ans = 0;
        dfs(link, visit, x[0], x[0], x[1], ans);
        answer = min(answer, abs(ans*2-n));
        //cout << num << " ** " << ans << " ** " << abs(ans*2-n) << "\n";
    }

    return answer;
}

바로 성공~~ 맨 처음 짠 아이디어가 완전 오류였다는걸 배운 하루~~