[백준 14889] 스타트와 링크

문제 바로가기

14889번: 스타트와 링크

백트래킹으로 스타트 팀과 링크 팀의 팀원을 구하고,

2중 for문으로 각 팀의 점수를 계산하여 차가 가장 작은 것을 구하면 된다.

 

 

처음 풀었을 때 시간초과가 떠서 띠용..

생각해보니 팀을 나누는 부분에서 중복계산이 있었다는 것을 찾았다.

 

 

- 시간초과가 난 dfs 코드

void dfs(int digit)
{
	if (digit == n / 2)
	{
		minn = min(minn, compare());
		return;
	}

	for (int i = 0; i < n; i++)
	{
		if (!visited[i])
		{
			visited[i] = 1;
			dfs(digit + 1);
			visited[i] = 0;
		}
	}
}

 

이 dfs 함수에 prev 인자를 추가해주었다. 이제껏 봤던 순서 다음부터 dfs를 진행하는 것이다.

 

- 고친 코드

void dfs(int prev, int digit)
{
	if (digit == n / 2)
	{
		minn = min(minn, compare());
		return;
	}

	for (int i = prev+1; i < n; i++)
	{
		if (!visited[i])
		{
			visited[i] = 1;
			dfs(i, digit + 1);
			visited[i] = 0;
		}
	}
}

 

- 코드 전체

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>

using namespace std;

int n;
int arr[20][20];
int visited[20];
int minn = 100;


int find_sum(vector<int> tmp)
{
	int sum = 0;

	for (int i = 0; i < tmp.size(); i++)
	{
		for (int j = i+1; j < tmp.size(); j++)
		{
			sum += arr[tmp[i]][tmp[j]];
			sum += arr[tmp[j]][tmp[i]];
		}
	}
	return sum;
}
int compare()
{
	vector<int> start;
	vector<int> link;

	int diff = 0;
	for (int i = 0; i < n; i++)
	{
		if (visited[i])
			start.push_back(i);
		else
			link.push_back(i);
	}

	diff = abs(find_sum(start) - find_sum(link));

	return diff;
}
void dfs(int prev, int digit)
{
	if (digit == n / 2)
	{
		minn = min(minn, compare());
		return;
	}

	for (int i = prev+1; i < n; i++)
	{
		if (!visited[i])
		{
			visited[i] = 1;
			dfs(i, digit + 1);
			visited[i] = 0;
		}
	}
}
int main()
{
	cin >> n;

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

	dfs(-1, 0);

	cout << minn << endl;
}