[맞음] 백준 14889 스타트와링크 c++ // dfs, 사람기준으로 생각하라. 일단 모든경우의수를 벌려놓고 생각하라, 비트마스킹

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

14889번: 스타트와 링크

1.의사코드

dfs(n) : n번째사람이 1팀으로가거나 2팀으로 가거나... 이진트리탐색

dfs(a, b) : 1팀들의 리스트, 2팀들의 리스트

계산부분 : 2중반복문으로 해결

v : 0 1 2

 i

j

(i,j) : 0,0/ 0,1 /0,2 /1,0 ...

 

2. 전체코드

#include <bits/stdc++.h>

using namespace std;

int N,M,arr[24][24];
int ret = 987654321;

//n번째사람이 1팀으로감or2팀으로감
void dfs(int n, vector<int> a,vector<int> b) {
	if (n == N) {
		//팀원숫자가 같은경우만 정답갱신
		if (a.size() == b.size()) {
			int asum = 0, bsum = 0;
			for (int i = 0; i < M; ++i) {
				for (int j = 0; j < M; ++j) {
					asum += arr[a[i]][a[j]];
					bsum += arr[b[i]][b[j]];
				}
			}
			ret = min(ret, abs(asum - bsum));
		}
		return;
	}
	//1팀으로가는경우
	a.push_back(n);
	dfs(n + 1, a, b);
	a.pop_back();

	//2팀으로가는경우
	b.push_back(n);
	dfs(n + 1, a, b);
	b.pop_back();
}
int main() {
	cin.tie(0);

	cin >> N;
	M = N / 2;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			cin >> arr[i][j];
		}
	}
	vector<int> v1, v2;
	dfs(0, v1,v2);
	cout << ret;
	return 0;
}

 

* 비트마스킹 풀이 (25.2.9.)

• 헷갈렸던 부분
  • 큰돌코드에서 i,j를 바꿔서 더해주는 부분이 없어서 왜 되는지 헷갈렸다.
•  
• 내 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll ret=987654321;
int n, a[24][24];

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);

   cin>>n;

   for(int i=0;i<n;++i) {
      for(int j=0;j<n;++j) {
         cin>>a[i][j];
      }
   }

   for(int subset=0;subset<(1<<n);++subset) {
      int cnt=0;
      vector<int> t1,t2;
      for(int i=0;i<n;++i) {
         if(subset & (1<<i)) {
            cnt++;
            t1.push_back(i);
         }
         else {
            t2.push_back(i);
         }
      }
      if(cnt!=n/2) continue; //팀은 절반씩 나눠야함

      //각 팀에서 2개씩 뽑아서 점수계산
      ll score1=0, score2=0;
      for(int i=0;i<n/2;++i) {
         for(int j=i;j<n/2;++j) {
            score1+=a[t1[i]][t1[j]];
            score1+=a[t1[j]][t1[i]]; //대칭행렬도 더해야함
            score2+=a[t2[i]][t2[j]];
            score2+=a[t2[j]][t2[i]];
         }
      }

      ll gab = abs(score1-score2);
      ret=min(ret,gab);
   }
   cout<<ret;

  
   
   return 0;
}

• 큰돌코드

#include <bits/stdc++.h>
using namespace std;
const int INF = 987654321;
int s[24][24], ret = INF, n; 
int go(vector<int>& a, vector<int> & b){
	pair<int, int> ret;  
	for(int i = 0; i < n / 2; i++){
		for(int j = 0; j < n / 2; j++){
			if(i == j)continue;
			ret.first += s[a[i]][a[j]];
			ret.second += s[b[i]][b[j]]; 
		}
	}
	return abs(ret.first - ret.second);
}
int main() { 
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> s[i][j];
        }
    } 
    for (int i = 0; i < (1 << n); i++) {
		if(__builtin_popcount(i) != n / 2) continue; 
        vector<int> start, link;
		for(int j = 0; j < n; j++){
			if(i & (1 << j))start.push_back(j);
			else link.push_back(j);
		}
		ret = min(ret, go(start, link)); 
    }
    cout << ret << '\n';
}