[C++] 백준 14889 - 스타트와 링크(백트래킹, DFS, 브루트포스, 무식하게 풀기)

0. [c++] 백준  -

https://www.acmicpc.net/problem/14889

1. 풀이

1) 팀을 매칭한다.

bool 배열을 활용해서 N/2명의 팀을 구분해준다.

true, false를 활용해 사람을 구분배치

추가적으로 우리는 모든 경우에 대해 분석을 할 예정이므로, DFS방식으로 탐색을 진행하도록 하였다.

또한 중복 탐색을 막기 위해서 pos라는 변수를 활용해 불필요한 탐색을 줄여주었다.

2) 매칭이 완료된 팀의 능력치를 구한다.

능력치를 간단히 더해주고, 각 팀의 전력 차를 구한 뒤, 최종 결과랑 비교하면 완료!

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

#include<iostream>   using namespace std;   int N, ret = 1000000007; int arr[21][21]; bool visited[21];   void matching(int num, int pos) {     if (num == N / 2) {         //a,b에는 각 팀의 능력치를 저장한다.         int a = 0, b = 0;         for (int i = 0;i < N;i++) {             //a팀은 visited==true인 팀이다.             if (visited[i]) {                 for (int j = i + 1;j < N;j++)                     //팀원간의 상호작용 능력치 합을 오름차순을 활용해 더해준다.                     if (visited[j])                         a += arr[i][j] + arr[j][i];             }             else {                 for (int j = i + 1;j < N;j++)                     if (!visited[j])                         b += arr[i][j] + arr[j][i];             }         }         //각 팀의 능력치 차를 더해준다.         if (ret > abs(a - b))             ret = abs(a - b);     }     else {         for (int i = pos;i < N;i++) {             visited[i] = true;             matching(num + 1, i + 1);             visited[i] = false;         }     } }   int main() {     cin.tie(0);     cin.sync_with_stdio(0);     cin >> N;     for (int i = 0;i < N;i++)         for (int j = 0;j < N;j++)             cin >> arr[i][j];       matching(0, 0);       cout << ret; } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!