전력망을 둘로 나누기 - 프로그래머스, c++

 

 

- 문제 풀이

"완전 탐색"을 사용하는 문제였다.

완전 탐색 중에서도 bfs를 구현해 문제를 해결했다.

 

 

- 코드

제출한 코드는 다음과 같다.

<bfs 구현 방법>

1. 주어진 데이터들을 vector에 넣어 탐색할 수 있도록 한다.

2. 두 점을 넣어 bfs 탐색을 통해 두 점사이에 연결된 점들의 개수를 구한다.

3. n - (2 * sum) 공식을 통해 연결된 점끼리의 차이 값을 계산, 그 중 가장 min 최솟값을 구한다.

#include <string>
#include <vector>
using namespace std;

// 탐색에 필요한 벡터 선언
vector<int> m[200];

// bfs 함수 (점togo부터 점now까지 탐색하며 이어진 점 개수 세기)
int bfs(int togo, int now, int count) {
    for (int i = 0; i < m[now].size(); i++) {
        if (m[now][i] != togo) {
            count = bfs(now, m[now][i], count+1);
        }
    }
    return count;
}

// main 함수
int solution(int n, vector<vector<int>> wires) {
	// 필요한 변수 선언
    int answer = 2000;
    
    // vector m에 주어진 wires 정보대로 선 연결하기
    for (auto w : wires) {
        m[w[0]].push_back(w[1]);
        m[w[1]].push_back(w[0]);
    }
    
    // bfs 함수 실행
    for (auto w : wires) {
   		//이어진 점 개수 세기
        int sum = bfs(w[0], w[1], 1); 
        // (전체 점 개수 - 현재 이어진 점 개수) 를 해 차이를 구할 수 있음
        int comp = n - (2 * sum);
        // 차이 중 최소 값 구하기
        answer = min(answer, abs(comp));
    }
    
    // 계산 값 반환
    return answer;
}

(코드 참고: https://ytlive.tistory.com/m/289 )