백준 14889 c++ "스타트와 링크" -PlusUltraCode-

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

 

 

[필자 사고]

여러명의 N명중 N/2명을 골라야 되는 문제이다.

즉 조합을 이용하여 해결해야 된다.

조합관련한 알고리즘은 재귀형태를 이용한 DFS방식을 사용 하면 된다.

 

필자는 처음에 N/2명을 조합으로 고른 뒤 다시

2명을 조합으로 고르는 형식으로 코드를 작성했다.

그 과정에서 많은 벡터들이 만들어지고 불필요한 코드들이 생겨 

결국 시간초과라는 결과를 얻었따.

 

곰곰히 생각해보니 2중 for문을 사용하면 굳이 2명정도는 조합을 사용하지 않아도

된다는걸 이 문제를 통해 크게 느끼게 되었다.

 

아래는 소스코드 해설이다.

 

 

• Input() 함수:
  이 함수는 입력 데이터를 처리합니다. 먼저 N명의 사람 수를 입력받고, N x N 크기의 능력치 행렬을 구성합니다. 이 행렬(arr)은 각 사람 간의 능력치를 저장하는 데 사용됩니다. 이후, 모든 능력치 데이터를 행렬에 채워 넣습니다.
• SelectMember(int idx, int count) 함수:
  이 함수는 팀을 선택하는 핵심 부분입니다. 재귀와 백트래킹을 사용하여 팀을 나누는 과정을 담당합니다.
  • count가 N/2에 도달했을 때:
    이미 팀의 절반이 선택되었으므로 두 팀의 능력치를 계산합니다. memberVisited 배열을 이용해 각 팀의 멤버를 구분하고, arr 행렬을 참조해 팀의 능력치 합을 구합니다. 두 팀의 능력치 차이를 계산하여 resultMinDiff 변수에 최소값을 갱신합니다.
  • 반복문과 재귀 호출을 통한 팀 구성:
    현재 인덱스부터 시작해 남은 사람들을 하나씩 선택합니다. 만약 해당 사람이 이미 선택된 상태라면 (memberVisited[i]가 true), 다음 사람으로 건너뜁니다. 그렇지 않다면 그 사람을 현재 팀에 추가하고 SelectMember 함수를 재귀 호출합니다. 이후 다시 원래 상태로 돌아가는 과정(백트래킹)을 통해 선택을 취소하고 다른 경로를 탐색합니다.
• GameStart() 함수:
  이 함수는 프로그램의 팀 나누기 과정을 시작합니다. SelectMember(0, 0)을 호출하여 인덱스 0부터 시작해 팀 구성 작업을 시작합니다. 여기서 첫 번째 인덱스와 선택된 사람 수(count)가 초기화된 상태로 재귀 탐색이 시작됩니다.

 

 

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>

using namespace std;

int N;
int resultMinDiff = INT_MAX;
vector<vector<int>> arr;
vector<bool> memberVisited;
vector<int> startTeam;
vector<int> linkTeam;

void Input() {
	cin >> N;
	arr.resize(N );
	memberVisited.resize(N);
	for (int i =0; i < N; i++) {
		arr[i].resize(N );
	}

	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			cin >> arr[i][k];
		}
	}
}

void SelectMember(int idx, int count) {
	
	if (count == N / 2) {
		int start, link;
		start = 0;
		link = 0;
		
		for (int i = 0; i < N; i++) {
			for (int k = 0; k < N; k++) {
				if (memberVisited[i] == true && memberVisited[k] == true)start += arr[i][k];
				if (memberVisited[i] == false && memberVisited[k] == false) link += arr[i][k];
			}
		}

		int temp = abs(start - link);
		if (resultMinDiff > temp)resultMinDiff = temp;

		return;
		
		
	}

	for (int i = idx; i < N; i++) {
		if (memberVisited[i] == true)continue;
		memberVisited[i] = true;

		startTeam.push_back(i);
		SelectMember(i+1, count+1); 
		startTeam.pop_back();

		memberVisited[i] = false;
	}
}


void GameStart() {
	SelectMember(0, 0);
}

int main(void) {
	Input();
	GameStart();
	cout << resultMinDiff;
}