[L2] 프로그래머스 전력망을 둘로 나누기 C++ BFS, 완전 탐색, 브루트포스 알고리즘

리뷰

프로그래머스

 

브루트포스 알고리즘으로 간선을 1개씩 지워가며 모든 경우의 그룹을 조회하여 그룹간 송신탑 개수의 차를 구하는 문제

 

 

전역 변수

• v : BFS시 방문배열로 사용하기 위한 정수형 배열

 

함수

1. bfs

int bfs(int node, const vector<vector<int>>& lst)

 

너비 우선 탐색을 통해 노드간 관계를 만들고, 각 노드에 방문 처리를 진행하는 함수

1. 매개 변수로 탐색을 시작할 노드 node와 인접 리스트 정보 lst를 입력받는다.
2. 정수형 큐 q를 초기화 하고 초깃값인 node를 push해준다.
3. node를 방문 처리 해주고, 그룹간 송신탑의 개수 cnt 개수를 1로 초기화 해준다.
4. q가 빌때까지 반복문을 실행하고 인접리스트에 존재하는 노드를 방문하고 방문처리 및 cnt를 증가시킨다.
5. 탐색이 종료되면 cnt를 출력해 준다.

 

문제풀이

1. answer을 가능한 큰 수로 초기화 해준다, 10의 9승정도면 적당하다.
2. n - 1개의 간선 정보를 순회한다, 인접 리스트용 2차원 정수형 벡터 lst를 n + 1크기로 초기화 해준다.
3. 이전에 방문했던 정보를 초기화 해야하니 memset메서드를 통해 방문배열 v를 0으로 초기화 해준다.
4. 다시 n - 1개의 간선 정보를 순회한다, 이때 i와 j가 동일할 경우 해당 간선은 제외해 준다.
5. 인접리스트 lst에 양방향 간선을 추가해 준다.
6. 그룹간 송신탑의 개수를 저장할 정수형 벡터 result를 초기화 한다.
7. n개의 노드를 순회하며 현재 방문처리 되지 않은 노드를 만났을 경우 bfs를 진행, 결과값을 result에 push해준다.
8. 탐색이 종료되었다면 answer와 두 그룹의 송신탑의 개수의 차를 비교하여 더 작은 값으로 최신화 해준다.
9. answer를 리턴해 준다.

 

참고 사항

송신탑은 싸이클이 없는 트리 구조이기 때문에 무조건 두 그룹으로 나뉘어지게 된다.

 

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

int v[101];

int bfs(int node, const vector<vector<int>>& lst) {
    queue<int> q;
    q.push(node);
    v[node] = 1;
    int cnt = 1;
    
    while (!q.empty()) {
        int cn = q.front(); q.pop();
        for (int nn : lst[cn]) {
            if (v[nn]) continue;
            v[nn] = 1;
            cnt++;
            q.push(nn);
        }
    }
    return cnt;
}

int solution(int n, vector<vector<int>> wires) {
    int answer = 1e9;
    
    for (int i = 0; i < n - 1; i++) {
        vector<vector<int>> lst(n + 1);
        memset(v, 0, sizeof(v));
        for (int j = 0; j < n - 1; j++) {
            if (i == j) continue;
            lst[wires[j][0]].push_back(wires[j][1]);
            lst[wires[j][1]].push_back(wires[j][0]);
        }
        
        vector<int> result;
        for (int j = 1; j <= n; j++) {
            if (v[j]) continue;
            result.push_back(bfs(j, lst));
        }
        answer = min(answer, abs(result[0] - result[1]));
    }
    
    return answer;
}