[백준] 14889 스타트와 링크

[백준14889]스타트와 링크

백트래킹과 bfs를 이용하여 풀었다.
완전탐색을 해야하는 문제이다.
가능한 모든 팀 조합을 구해서 각각의 능력치를 계산해 비교해야한다.
1. 스타트팀으로 정할 선수를 뽑는다. (n이 짝수이므로 스타트팀만 정해주고, 나머지는 자동으로 링크팀으로 들어간다.)
2. 선수가 N/2명이 되면 능력치를 계산한다

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int N;
int S[20][20];
int answer = 1000000000;
bool back_tracking[20]; //각 인원이 사용 되었는지 사용되지 않았는지

//cnt:뽑은 명수
void BFS(int curplayer, int cnt) {
	//N/2명 뽑았으면 차이를 계산
	if (cnt == N/2) {
		//BFS를 통해 능력치 계산
		vector<int> start_team;
		vector<int> link_team;

		for (int i = 0; i < N; i++) {
			if (back_tracking[i] == true) {
				start_team.push_back(i);
			}
			else {
				link_team.push_back(i);
			}
		}

		int capa_start = 0;
		int capa_link = 0;
		//bfs로 능력치 차이 계산
		for (int i = 0; i < start_team.size(); i++) {
			for (int j = i+1; j < start_team.size(); j++) {
				int start_x = start_team[i];
				int start_y = start_team[j];
				int link_x = link_team[i];
				int link_y = link_team[j];
				capa_start += S[start_x][start_y] + S[start_y][start_x];
				capa_link += S[link_x][link_y] + S[link_y][link_x];
			}

		}

		//능력치 비교
		answer = min(answer, abs(capa_start - capa_link));
		return;
	}


	for (int i = curplayer ; i < N; i++) {
		if (back_tracking[i] == 0) { //사용되지 않은 인원이면
			back_tracking[i] = true;
			BFS(i, cnt + 1);
			back_tracking[i] = false;
		}
	}
}

int main() {
	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &S[i][j]);
		}
	}


	BFS(0, 0);
	printf("%d", answer);
	
	return 0;
}