[백트래킹] [비트마스크]14889 스타트와 링크

스타트와 링크 (14889)

 

풀이코드 (브루트 포스)

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 14889 스타트와 링크
int INF = -123456789;
int N;
int board[20][20];
// person 은 몇 번째 사람인지를 links 는 link 팀의 구성원들
int solve(int person, vector<int> &links, vector<int> &starts){
	// 기저사례 : person 이 N-1을 마치고 N 번째가 됐다면 끝
	if(person == N){
		// 기저사례 : 팀이 절반씩이 아니라면 땡
		if(links.size() != N/2 || starts.size() != N/2) return INF;
		
		int t1 = 0;
		int t2 = 0;
		for(int i = 0; i < N/2; i++){
			for(int j = 0; j < N/2; j++){
				if(i == j) continue;
				t1 += board[links[i]][links[j]];
				t2 += board[starts[i]][starts[j]];
			}
		}
		return abs(t1-t2);
	}
	
	int ans1 = 0, ans2 = 0;
	
	// link 팀에 넣기
	links.push_back(person);
	ans1 = solve(person + 1, links, starts);
	links.pop_back();
	
	// start 팀에 넣기
	starts.push_back(person);
	ans2 = solve(person + 1, links, starts);
	starts.pop_back();
	
	int ans;
	
	if(ans1 == INF || ans2 == INF) return ans1 < ans2 ? ans2 : ans1;
	else return ans1 < ans2 ? ans1 : ans2;
	
	
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	cin >> N;
	
	for(int i = 0 ; i < N; i++){
		for(int j = 0 ; j < N; j++){
			cin >> board[i][j];
		}	
	}
	vector<int> a1, a2;
	cout << solve(0, a1, a2) << '\n';
	
}

 

해설

---

적용한 레시피 / 방법론 + 접근법

 

풀이

 

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

- 위의 코드처럼 모든 경우를 순회하여 답을 도출한 것이 브루트 포스이다. 지금까지 해온 것과 같은 형식이다.

그러나, 백트래킹 은 여기에 어떠한 조건을 추가하여 재귀 중간에 재귀를 끊을 수 있다.

여기서는 어떠한 조건을 추가해줄 수 있을까?

한 팀이라도 구성원의 수가 N / 2를 넘어가면 중단한다. 라는 조건을 추가할 수 있다. 이렇게 한다면 계산을 더욱 줄일 수 있게 된다. 다른 것은 동일하며 조건 하나만을 추가하였다. 또한, ans 를 return 할 때의 로직을 좀 더 명확하게 바꾸엇다.

 

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 14889 스타트와 링크
int INF = -123456789;
int N;
int board[20][20];
// person 은 몇 번째 사람인지를 links 는 link 팀의 구성원들
int solve(int person, vector<int> &links, vector<int> &starts){
	// 백트래킹 조건 : 두 팀 중 하나의 팀의 구성원이 N / 2를 넘으면 땡
	if(links.size() > N/2 || starts.size() > N/2) return INF;
	
	// 기저사례 : person 이 N-1을 마치고 N 번째가 됐다면 끝
	if(person == N){
		// 기저사례 : 팀이 절반씩이 아니라면 땡
		if(links.size() != N/2 || starts.size() != N/2) return INF;
		
		int t1 = 0;
		int t2 = 0;
		for(int i = 0; i < N/2; i++){
			for(int j = 0; j < N/2; j++){
				if(i == j) continue;
				t1 += board[links[i]][links[j]];
				t2 += board[starts[i]][starts[j]];
			}
		}
		return abs(t1-t2);
	}
	
	int ans1 = 0, ans2 = 0;
	int ans = INF;
	// link 팀에 넣기
	links.push_back(person);
	ans1 = solve(person + 1, links, starts);
	links.pop_back();
	
	if (ans == INF || (ans1 != INF && ans > ans1)) {
        ans = ans1;
    }
	
	// start 팀에 넣기
	starts.push_back(person);
	ans2 = solve(person + 1, links, starts);
	starts.pop_back();
	
	if (ans == INF || (ans2 != INF && ans > ans2)) {
        ans = ans2;
    }
	
	return ans;
	
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	cin >> N;
	
	for(int i = 0 ; i < N; i++){
		for(int j = 0 ; j < N; j++){
			cin >> board[i][j];
		}	
	}
	vector<int> a1, a2;
	cout << solve(0, a1, a2) << '\n';
	
}

하지만, 백트래킹 조건을 추가한 뒤에도 시간이 줄지는 않았다. 그래도 문제마다 상이할 것이므로 백트래킹 할 수 있다면 사용해보자.

풀이코드 (비트마스크)

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 14889 스타트와 링크
int INF = 123456789;
int N;
int board[20][20];


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	cin >> N;
	
	for(int i = 0 ; i < N; i++){
		for(int j = 0 ; j < N; j++){
			cin >> board[i][j];
		}	
	}
	
	int ans = INF;
	vector<int> link;
	vector<int> start;
	
	for(int bm = 1; bm < (1 << N); bm++){
		// 각 팀 검사
		for(int i = 0; i < N; i++){
			if(bm & (1 << i)) {
				link.push_back(i);
			} else {
				start.push_back(i);
			}
		}
		// 딱 절반이 아니면 continue
		if(link.size() != (N / 2)) {
			link.clear();
			start.clear();
			continue;
		}
		int t1 = 0;
		int t2 = 0;
		for(int i = 0; i < N/2; i++){
			for(int j = 0; j < N/2; j++){
				if(i == j) continue;
				t1 += board[link[i]][link[j]];
				t2 += board[start[i]][start[j]];
			}
		}
		
		ans = ans > abs(t1 - t2) ? abs(t1 - t2) : ans;
		
	}
	
	
	cout << ans << '\n';
	
}

재귀를 사용하지 않고, 비트마스크를 이용하여 팀을 나누는 모든 경우의 수를 구해본 풀이이다.

bm 을 비트마스크로 썼다. bm 에서 1이라면 link 에 0 이라면 start 팀에 넣는 식으로 하였으며, 나머지 합의 차를 구하는 과정은 상동이다.

더 빨라지지는 않았다. 백트래킹 조건을 빼서 그런듯 하다.