[Algo Rhythm🕺💃]BOJ 14889 - 스타트와 링크

문제 분석

스타트팀을 $T_{start}$, 링크팀을 $T_{link}$ 그리고 두 팀의 능력치를 각각 $S_{start}, S_{link}$라고 하자. 이때 각 팀에 속하는 사람들의 수는 두 팀 모두 축구를 하는 $N\ (4 \le N \le 20)$명의 절반인 $N / 2$ 명이다.

문제에서 요구하는 $min(|S_{start} - S_{link}|)$를 구하기 위한 가장 직관적인 방법은 $(T_{start}, T_{link})$의 모든 조합을 구한 뒤 각 조합의 $|S_{start} - S_{link}|$을 구하고 그 중 최소값을 찾는 것이다.

모든 조합을 구해야 하는 문제들은 주로 'backtracking'을 사용한다. 이 문제도 마찬가지로 backtracking을 사용하여 해결했다.

 

문제 풀이

축구를 하는 사람들마다 고유의 id가 있고 그것들을 각각 1, 2, ... , N이라고 하자. 그리고 각 id를 하나의 vertex라고 생각해보자.

그렇다면 우리는 $(T_{start}, T_{link})$의 모든 조합을 구하는 문제가 결국 (선택한 N / 2개의 vertex, 선택하지 않은 N / 2개의 vertex)의 모든 조합을 구하는 문제와 같다는 사실을 알 수 있다. vetex들을 선택할 때는 이미 선택되지 않은 vertex들만 선택하고 이때 쓰이는 점화식은 다음과 같다.

 

$f(id, n_{member}, N) = \begin{cases}calc\ |S_{start} - S_{link}|\ and\ compare&if\ n_{member} == N / 2&(base\ case)\\f(id + 1, n_{member} + 1, N)&else\ if\ vertex_{id + 1}\ is\ not\ visited&(recursive\ case)\end{cases}​$

 

이때 주의할 점은 모든 조합을 구하기 위해 1부터 N까지 backtracking할 필요가 없다는 것이다. 왜냐하면 N / 2개의 vertex만 선택하면 나머지 N / 2개의 vertex들은 자동으로 결정되기 때문이다. 따라서 N / 2개의 vertex만 backtracking하여 문제를 해결하도록 구현해야 한다.

예를 들어 4개의 vertex 중 2개를 선택하면 가능한 조합은 $(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)$이렇게 6개이다. 하지만 $(1, 2)$ 선택시 선택되지 않는 vertex들은 자연스럽게 $(3, 4)$가 되는 것을 알 수 있다.

 

복잡도 분석

n명의 사람들이 축구를 한다고 할 때 복잡도는 아래와 같다.

 

시간 복잡도 : $O(n!)$

- recursive call을 $i$번 했을 때 각 recursive call마다 선택할 수 있는 id 즉, vertex가 $N - i$개 존재하기 때문이다.

 

공간 복잡도 : $O(n^2)$

- 같은 팀일때 능력치를 기록한 2차원 배열 : $O(n^2)$

- n개의 vertex에 대한 visit 여부를 기록하는 배열 : $O(n)$

- $T_{start}, T_{link}$에 대한 정보를 가지는 vertor : $O(n)$

 

코드

	#include <cstdio>
	#include <cstring>
	#include <climits>
	#include <cstdlib>
	#include <algorithm>
	#include <vector>
	#define MAX_NUM 20
	using namespace std;
	vector<int> team_start;
	vector<int> team_link;
	int S[MAX_NUM + 1][MAX_NUM + 1];
	bool visited[MAX_NUM + 1];
	int ans = INT_MAX;
	void backtrack(int id, int n_member, int N)
	{
	if (n_member == N / 2)
	{
	int S_start = 0, S_link = 0;
	int mem_i, mem_j;
	for (int i = 1; i <= N; i++)
	{
	if (visited[i])
	team_start.push_back(i);
	else
	team_link.push_back(i);
	}
	for (int i = 0; i < team_start.size(); i++)
	{
	mem_i = team_start[i];
	for (int j = i + 1; j < team_start.size(); j++)
	{
	mem_j = team_start[j];
	S_start += (S[mem_i][mem_j] + S[mem_j][mem_i]);
	}
	}
	for (int i = 0; i < team_link.size(); i++)
	{
	mem_i = team_link[i];
	for (int j = i + 1; j < team_link.size(); j++)
	{
	mem_j = team_link[j];
	S_link += (S[mem_i][mem_j] + S[mem_j][mem_i]);
	}
	}
	ans = min(ans, abs(S_start - S_link));
	team_start.clear();
	team_link.clear();
	return;
	}
	for (int i = id + 1; i <= N; i++)
	{
	if (!visited[i])
	{
	visited[i] = true;
	backtrack(i, n_member + 1, N);
	visited[i] = false;
	}
	}
	}
	int main()
	{
	int N, _s;
	memset(visited, false, sizeof(visited));
	scanf("%d", &N);
	for (int i = 1; i <= N; i++)
	{
	for (int j = 1; j <= N; j++)
	{
	scanf("%d", &_s);
	S[i][j] = _s;
	}
	}
	for (int i = 1; i < N / 2; i++)
	{
	visited[i] = true;
	backtrack(i, 1, N);
	visited[i] = false;
	}
	printf("%d", ans);
	return 0;
	}

view raw boj_14889.cpp hosted with ❤ by GitHub

 

문제 출처 및 원본 문서

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

14889번: 스타트와 링크

https://www.notion.so/BOJ-14889-cb96bb89dce24aa88b7b955bc050c074

BOJ 14889 - 스타트와 링크