[DFS] 14889 스타트와 링크 C++

Seunghyeon·2022년 12월 27일

백준 문제 푼다.

목록 보기

4/21

고통받은 흔적

고작 실버2 문제에 이렇게 스트레스를 받을 이유가 없는데 왜 안되나 계속 돌려도 테스트 케이스들은 다 맞았다.

풀이

팀원들을 넣는 경우의 수를 dfs로 돌려야 한다.
그러면 팀원들을 짜는 조합인데 중복이면 안된다. (1, 1, 1)이 들어가면 안됨
그래서 dfs 내 반복하기 위한 (visited를 1로 만들어 1번 팀으로 만들기 위한)
for 문이 중요한데

굳이 반복하지 않아도 되는 인덱스는 넣지 않도록 설계하는것이 중요하다.

처음에 이것때문에 시간초과가 몇번 나서 백준의 시간 기준이 참 미워졌었다.

cmath의 절대값을 구해주는 abs 함수를 사용하는것도 도움이 된다.

풀이 코드

#include <bits/stdc++.h>

#define endl "\n"

using namespace std;

int n;

int arr[21][21] = {0, };

int Min = 999999999;

int team1[10];
int team2[10];

vector<int> t1;
vector<int> t2;


int team1sum = 0;
int team2sum = 0;

int visited[21] = { 0, };

void dfs(int cnt, int pos)
{
	if (cnt == n/2)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (i != j && visited[i] == 1 && visited[j] == 1)
				{
					team1sum += arr[i][j];
				}
				if (i != j && visited[i] == 0 && visited[j] == 0)
				{
					team2sum += arr[i][j];
				}
			}
		}

		if (Min > abs(team1sum - team2sum))
		{
			Min = abs(team1sum - team2sum);
		}
		return;
	}

	for (int i = pos; i < n; i++)
	{
		if (!visited[i])
		{
			visited[i] = 1;
			dfs(cnt + 1, i+1);
			visited[i] = 0;
			team1sum = 0;
			team2sum = 0;
		}
	}
}


int main()
{
	cin >> n;

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

	dfs(0, 0);

	cout << Min;

	return 0;
}