[C++][백준] - 링크와 스타트 (15661번)

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

15661번: 링크와 스타트

🔔 문제 : 

축구게임을 하기 위한 사람 N명이 주어집니다. ( 4<= N <= 20)

 

그리고 각 사람마다 시너지를 점수화한 점수판이 주어집니다.

 

예를들면 이런식으로 주어집니다.

i/j	1	2	3	4
1	0	1	2	3
2	4	0	5	6
3	7	1	0	2
4	3	4	5	0

 

i, j 는 사람의 번호를 의미하고 그에 맞는 수들은 시너지를 의미합니다.

 

이 시너지가 최솟값이 되는 팀을 짜서 최솟값을 구하는 문제입니다.

 

시너지는 1 <= x <= 100인 정수이고, 두 팀은 인원수는 같지 않아도 되지만 한 명 이상이여야 합니다.

---

🔔 Kick Point :

사람을 뽑는 것이기 때문에 사람을

DFS를 이용하여 뽑으면서 조건에 맞게 추리면 됩니다.

 

DFS가 이뤄지는 순서는 

G_visited 배열이 A팀의 사람이라 생각하고

 

1명부터 N/2명까지 각 팀에 해당하는 숫자에 맞게 구해주면 됩니다.

 

조합에 대해 자세한 알고리즘을 알고싶으면 이 포스팅을 참고해주세요

2022.03.03 - [백준] - [C++][백준] - N과 M (2) (15650번)

[C++][백준] - N과 M (2) (15650번)

---

변수

G_power[MAX][MAX] : 사람간의 시너지 점수

G_visited[MAX] : A팀의 선택된 사람 (한 팀을 알면 자연스럽게 B팀을 알수있다)

G_n : 사람 숫자 N명

G_Result : 시너지 최솟값 (초기값 10000000 은 최댓값 20*20*100 보다 크기 위해 만듬)

 

함수

Input : G_power인 시너지 점수를 입력

Cal : a팀과 b팀의 시너지 점수를 계산하여 빼줘서 최솟값을 구함

DFS : 재귀적 방법의 백트래킹을 사용하여 팀의 경우의 수를 구함

Sol : 1명부터 N/2명까지 팀을 선별하며 문제를 진행해가는 함수이며 G_Result를 출력함

🔔 Code :

#include <iostream>
#include <cmath>
#define endl '\n'
#define MAX 20

using namespace std;

int G_power[MAX][MAX];
bool G_visited[MAX] = { false, };
int G_n;
int G_Result = 100000000;


void Input(int n = 0) {
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {

			cin >> G_power[i][j];

		}
	}
}

int Cal() {
	int aTeam = 0;
	int bTeam = 0;

	// aTeam;
	for (int i = 0; i < G_n; i++) {
		for (int j = 0; j < G_n; j++) {
			if (G_visited[i] && G_visited[j]) {
				aTeam += G_power[i][j];
			}
		}
	}	
	// bTeam;
	for (int i = 0; i < G_n; i++) {
		for (int j = 0; j < G_n; j++) {
			if (!G_visited[i] && !G_visited[j]) {
				bTeam += G_power[i][j];
			}
		}
	}


	return (abs(aTeam - bTeam));
}

void DFS(int cnt = 0, int num = 0, int n =0) {
	
	if (cnt == num) {
		int tmp = Cal();
		if (tmp < G_Result) G_Result = tmp;
		return;
	}

	for (int i = n; i < G_n; i++) {

		if (!G_visited[i]) {
			G_visited[i] = true;
			DFS(cnt + 1, num, i+1);
			G_visited[i] = false;
		}
	}
}

void Sol() {

	for (int i = 1; i <= G_n / 2; i++) {
		DFS(0, i, 0);
		for (int i = 0; i < G_n; i++) { G_visited[i] = false; }

	}

	cout << G_Result;
}


int main() {

	cin >> G_n;
	Input(G_n);
	Sol();

}

---