BaekJoon 14889번: 스타트와 링크

풀이법

1) N=20일 경우 시간 초과가 발생할 수 있으니 이를 고려해야 코딩해야 한다.

2) dfs와 백트래킹을 이용해서 모든 경우의 수를 돌아보는 완전 탐색 문제이다.

3) 백트래킹을 이용하여 스타트 팀으로 뽑을 선수 번호를 뽑는 것을 반복한다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define INF 1000000001
using namespace std;
int n;
int arr[21][21];
bool visited[21];
int ans = INF;
void backtracking(int player, int level)
{
	if (level == n / 2)
	{
		vector<int> start;
		vector<int> link;
		int sumLink = 0;
		int sumStart = 0;
		for (int i = 1; i <= n; i++)
		{
			if (visited[i])
				start.push_back(i);
			else
				link.push_back(i);
		}
		for (int i = 0; i < start.size(); i++)
		{
			for (int j = i+1; j < start.size(); j++)
			{
				sumStart += arr[start[i]][start[j]] + arr[start[j]][start[i]];
				sumLink += arr[link[i]][link[j]] + arr[link[j]][link[i]];
			}
		}
		ans = min(ans, abs(sumStart - sumLink));
	}
	for (int i = player + 1; i <= n; i++)
	{
		if (visited[i])
		{
			continue;
		}
		visited[i] = true;
		backtracking(i, level + 1);
		visited[i] = false;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> arr[i][j];
		}
	}
	backtracking(0, 0);
	cout << ans;
}

한계점 및 개선사항 (+주의사항)

초기 접근이 어려워서 시간이 오래걸렸다. 재귀 호출에 관한 이해도가 높아졌다고 생각했는데 실생활 예제로 적용하는 부분에서 많이 막혔다. 재귀는 항상 return 값과 반복을 어떻게 짜고, 매개변수에 어떤 것을 넣을지를 잘 고려해야 하는 것 같다.

 

github.com/pearlcrum/CodingTest/tree/main

pearlcrum/CodingTest