(프로그래머스 c++)위클리 챌린지 9주차

https://programmers.co.kr/learn/courses/30/lessons/86971?language=cpp 

코딩테스트 연습 - 9주차

bfs를 활용한 문제 풀이.

 

우선 주어진 wires 벡터로 그래프를 그려 주도록 하자.

이후 한 노드를 선택해 연결 되어 있는 노드를 끊고 BFS 탐색을 진행하여 끊은 노드의 개수를 구하면 된다.

이때, n * n 크기의 visited 벡터를 만들어, 이미 끊었던 간선을 다시 끊는 일이 없도록 가지를 친다.

 

bfs() 함수에 그려 놓았던 그래프와 n, 현재 노드 번호를 전달하여 진행한다.

노드 방문 여부를 알 수 있도록 visited 벡터 선언.

현재 노드 번호를 큐에 넣고, visited 또한 true로 바꿔서 bfs를 진행.

큐에 담겨있는 노드가 연결되어 있는 노드들은 모두 currentNode와 연결된 노드를 뜻하게 된다.

이를 cnt로 개수를 구하면, n - cnt는 다른 한 쪽의 송전탑의 개수가 된다.

 

이 둘의 차이를 절대값으로 구해 answer와 비교하면서 갱신하면 끝!

 

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <iostream>

using namespace std;

int answer = 9999;

void bfs(vector<vector<bool>> graph, int n, int currentNode){
    vector<bool> visited(n + 1, false);
    queue<int> q;
    int cnt = 0;
    
    q.push(currentNode);
    visited[currentNode] = true;
    
    while(!q.empty()){
        int node = q.front();
        
        q.pop();
        
        cnt++;
        
        for(int i = 1; i <= n; i++){
            if(!visited[i] && graph[node][i]){
                visited[i] = true;
                q.push(i);
            }
        }
    }
    
    answer = answer > abs(cnt - (n - cnt)) ? abs(cnt - (n - cnt)) : answer;
}

int solution(int n, vector<vector<int>> wires) {
    vector<vector<bool>> graph(n + 1, vector<bool>(n + 1, false));
    vector<vector<bool>> visited(n + 1, vector<bool>(n + 1, false));
    
    for(int i = 0; i < wires.size(); i++){
        int start = wires[i][0];
        int end = wires[i][1];
        
        graph[start][end] = true;
        graph[end][start] = true;
    }
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(!visited[i][j] && graph[i][j]){
                visited[i][j] = true;
                visited[j][i] = true;
                
                graph[i][j] = false;
                bfs(graph, n, i);
                graph[i][j] = true;   
            }
        }
    }
    
    return answer;
}