99클럽 코테 스터디 17일차 TIL - 프로그래머스 전력망을 둘로 나누기

 

 

#include <bits/stdc++.h>
#define MAX 101
using namespace std;

int cnt;

vector<int> graph[MAX];

void bfs(int v1, int v2){
    queue<int> q;
    vector<bool> visited(MAX);
    q.push(v1);
    visited[v1] = true;
    visited[v2] = true;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        
        for (int i=0; i<graph[node].size(); i++) {
            int node2 = graph[node][i];
                                                 
            if (visited[node2]) continue;
            
            cnt++;
            q.push(node2);
            visited[node2] = true;
        }
    }
}

int solution(int n, vector<vector<int>> wires) {
    
    int answer = MAX;
    for(auto wire:wires){
        graph[wire[0]].push_back(wire[1]);
        graph[wire[1]].push_back(wire[0]);
        
    }
    for(auto wire:wires){
        cnt = 1;
        int v1 = wire[0];
        int v2 = wire[1];
        bfs(v1,v2);
        answer = min(answer, abs(cnt*2-n));
    }
    
    
    return answer;
}

bfs 이용해서 풀이

 

 

 

오늘의 회고

• 해야하는걸 꾸준히 열심히 하자
• 내일(4/18) 학습 예정 : 스프링부트 로그인 (spring security 이용)