[BOJ] 백준 14889번 스타트와 링크 C++(삼성 기출문제)

문제

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

14889번: 스타트와 링크

삼성 SW 역량 테스트 기출 문제라고 한다. 문제의 80%정도까지 접근은 했지만 문제 이해를 잘못하고, 변수 초기화를 깜빡해서 시간을 많이 날렸다. 문제 자체는 그렇게 어렵지 않았다. 앞으로 문제를 잘 읽고 접근하도록 하자.

풀이

이 문제는 백트래킹의 응용 문제라고 할 수 있다.

보드의 크기(N)에 대해 N/2개의 대한 조합을 백트래킹으로 구하고 사용된 값/사용되지 않은 값으로 나누어서 각각 start/link 백터에 삽입해주었다. 백터에 삽입된 좌표값을 바탕으로 start팀과 link팀의 점수를 구해주고 두 팀의 점수 차이를 절대값으로 받아서 result에 최솟값을 저장해주었다.

이러한 방식으로 모든 조합에 대해 계속 최솟값을 구해주고 모든 조합에 대해 값을 받아오면 result를 출력하고 프로그램을 종료해주었다.

이 문제에서 내가 간과했던 점은 (1,1), (2,2) ... (n, n)-> 보드의 x좌표와 y좌표가 같으면 보드의 값이 0이라는 점이다.

예를들어 start 백터에 1, 3, 5가 들어왔을때 이 모든 값들에 대해 순열을 돌리며 값을 더해줄 필요 없이 2중 for문으로 값을 더해줘도 상관이 없다는 얘기이다. 

처음에 문제를 접했을때 조합을 돌리고 이후 start/link 백터에 들어온 값에 대해 순열까지 돌리며 접근했지만 이는 필요없는 과정이라는 것이다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

int board[22][22];
int result = 100001;
vector<int> startVec;
vector<int> linkVec;
int arr[21];
bool isused[21];
int n;

void func(int idx, int cnt)
{
	int startSum = 0;
	int linkSum = 0;

	if (cnt == n / 2)
	{
		for (int i = 0; i < n; i++)
		{
			if (isused[i])
			{
				startVec.push_back(i);
			}
			else
			{
				linkVec.push_back(i);
			}
		}
		
		for (int i = 0; i < n / 2; i++)
		{
			for (int j = 0; j < n / 2; j++)
			{
				startSum += board[startVec[i]][startVec[j]];		
				linkSum += board[linkVec[i]][linkVec[j]];
			}
		}
		result = min(result, abs(startSum - linkSum));
		startVec.clear();
		linkVec.clear();
		return;
	}

	for (int i = idx; i < n; i++)
	{
		if (!isused[i])
		{
			isused[i] = true;
			func(i + 1, cnt + 1);
			isused[i] = false;
		}
	}
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(0);

	cin >> n;

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

	func(0, 0);

	cout << result;
}