Algorithm - 백트래킹 문제 풀이

백준 문제를 풀고 리팩토링 해봤다.

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

첫 시도는 dfs로 구현하려고 시도했지만 실패했다. 허허

그래서 강의에서 배운 백트래킹 방식으로 풀이해봤다.

저번에 배웠던 백트래킹 방식처럼 재귀를 사용했고, 팀이 완성되면 두 팀의 점수 차이를 구한다.

첫 풀이

vector<bool> used;
vector<vector<int>> synerge;
stack<int> s;
int minDiff = INT_MAX;
int halfN;

int GetDiff() 
{ 
	int size = synerge.size();
	int diff = 0; for (int i = 0; 
	i < size; ++i) 
	{ 
		for (int j = 0; j < size; ++j)
		{ 
			if (used[i] == used[j]) 
			{ 
				if (used[i]) diff += synerge[i][j];
				else diff -= synerge[i][j];
			} 
		} 
	} 
	
	return abs(diff); 
}

void BackTrack() 
{ 
	if (s.size() == halfN) 
	{ 
		int diff = GetDiff(); 
		if (minDiff > diff) minDiff = diff;
		return; 
	} 
	
	for (int i = 0; i < used.size(); ++i) 
	{ 
		if (used[i]) continue; 
		used[i] = true; 
		s.push(i); 
		BackTrack(); 
		s.pop(); 
		used[i] = false; 
	} 
	
} 

int main() 
{ 
	int n; 
	cin >> n;
	
	halfN = n / 2; 
	synerge.resize(n); 
	used.resize(n, false); 
	
	for (int i = 0; i < n; ++i) 
	{ 
		for (int j = 0; j < n; ++j) 
		{ 
			int num; 
			cin >> num; 
			synerge[i].push_back(num);
		}
	} 
	
	BackTrack();
	cout << minDiff; 
}

개선할 부분이 있어서 몇 가지 수정해봤다.

GetDiff 함수 수정

int GetDiff() 
{ 
	int size = synerge.size();
	int diff = 0; for (int i = 0; 
	i < size; ++i) 
	{ 
		for (int j = 0; j < size; ++j)
		{ 
			if (used[i] == used[j]) 
			{ 
				if (used[i]) diff += synerge[i][j];
				else diff -= synerge[i][j];
			} 
		} 
	} 
	
	return abs(diff); 
}

두 팀의 시너지를 구해 차이를 구하는 방식으로 구현했었다.
이 방식은 i와 j가 같은 팀이면 연산이 가능하기에 필요없는 반복이 들어있다.

때문에 미리 팀마다 배열을 만들어 분류하여 불필요한 조건 검사를 제외했다.

int GetDiff()
{
	int size = synerge.size();
	int diff = 0;

	vector<int> startTeam, linkTeam;

		for (int i = 0; i < size; ++i) // 팀마다 배열로 분류
	{
		if (used[i]) startTeam.push_back(i);
		else linkTeam.push_back(i);
	}


	for (int i = 0; i < halfN; ++i) // 한 팀의 팀원 수는 halfN
	{
		for (int j = 0; j < halfN; ++j)
		{
			diff += synerge[startTeam[i]][startTeam[j]] - synerge[linkTeam[i]][linkTeam[j]]; // 두 팀의 시너지 차이를 누적 계산
		}
	}

	return abs(diff);
}

Index 추가 및 Stack 제거

void BackTrack() 
{ 
	if (s.size() == halfN) 
	{ 
		int diff = GetDiff(); 
		if (minDiff > diff) minDiff = diff;
		return; 
	} 
	
	for (int i = 0; i < used.size(); ++i) 
	{ 
		if (used[i]) continue; 
		used[i] = true; 
		s.push(i); 
		BackTrack(); 
		s.pop(); 
		used[i] = false; 
	} 
	
} 

백트래킹 하는 함수에서 깊이를 검사하기 위해 스택을 사용했었다.
하지만 단순히 깊이만 저장한다면 int만 사용하면 되기에 수정했다.

void BackTrack(int index, int count)
{
	if (count == halfN)
	{
		int diff = GetDiff();
		if (minDiff > diff) minDiff = diff;
		return;
	}
	// 아래는 생략
}

매개변수에 넣어서 따로 뺄 필요가 없다.

또한 새로운 팀원을 추가할 때도

	for (int i = 0; i < used.size(); ++i) 
	{ 
		if (used[i]) continue; 
		used[i] = true; 
		s.push(i); 
		BackTrack(); 
		s.pop(); 
		used[i] = false; 
	} 

왼쪽부터 탐색했기 때문에 이미 지나간 자리는 검사할 필요가 없어 수정했다.

	for (int i = index; i < used.size(); ++i)
	{
		if (used[i]) continue;

		used[i] = true;

		BackTrack(i, count + 1);
		
		used[i] = false;
	}

수정본

#include <string>
#include <iostream>
#include <vector>

using namespace std;

vector<bool> used;
vector<vector<int>> synerge;

int minDiff = INT_MAX;
int halfN;

int GetDiff()
{
	int size = synerge.size();
	int diff = 0;

	vector<int> startTeam, linkTeam;

	for (int i = 0; i < size; ++i)
	{
		if (used[i]) startTeam.push_back(i);
		else linkTeam.push_back(i);
	}


	for (int i = 0; i < halfN; ++i)
	{
		for (int j = 0; j < halfN; ++j)
		{
			diff += synerge[startTeam[i]][startTeam[j]] - synerge[linkTeam[i]][linkTeam[j]];
		}
	}

	return abs(diff);
}

void BackTrack(int index, int count)
{
	if (count == halfN)
	{
		int diff = GetDiff();
		if (minDiff > diff) minDiff = diff;
		return;
	}

	for (int i = index; i < used.size(); ++i)
	{
		if (used[i]) continue;

		used[i] = true;

		BackTrack(i, count + 1);
		
		used[i] = false;
	}
}

int main()
{
	int n;
	cin >> n;

	halfN = n / 2;
	synerge.resize(n, vector<int>(n));
	used.resize(n, false);

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

	BackTrack(0, 0);

	cout << minDiff;
}