[백준][C++] 14889 스타트와 링크 - 실버1

문제 보기

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

14889번: 스타트와 링크

 

문제                           

 

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

	1	2	3
4		5	6
7	1		2
3	4	5

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S12 + S21 = 1 + 4 = 5
• 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S13 + S31 = 2 + 7 = 9
• 링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

 

 

입력                          

 

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

 

출력                          

 

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

 

풀이방법                 

 

DFS와 백트래킹을 사용하는 되는 문제이다.

비슷하게 백트래킹을 이용하는 문제는 저번에도 포스팅 한 적이 있다.

https://mountain-noroo.tistory.com/16

[백준][C#] 15649 N과 M (1) - 실버3

 

N과 M 시리즈는 백트래킹을 쉽고 재미있게 익힐 수 있는 좋은 문제들이라고 생각하니

이번 문제가 어려웠다면 해당 시리즈부터 쭉 풀어보는 것을 추천한다.

 

따라서 이 포스팅에서는 자세한 원리는 생략하겠다.

 

 

그래서 이 문제에 어떻게 백트래킹을 적용하면 될까?

 

 

 

2차원 배열로 입력이 들어오지만 일단 지금은 신경 쓸 필요가 없다.

일단 선수들은 1차원으로 나타낼 수 있음에 주목하자.

전력의 차를 구하는 것은 나중 문제고, 일단 팀을 나눌 수 있는 모든 케이스를 구해보는 것이 먼저다!

 

void DFS(int** arr, bool visited[], int index, int N, int count, int* min)
{
	if (count == N/2)
	{
		// 여기서 전력의 차를 구할 건데
        // 일단 나중에 생각하기

		return;
	}

	// 모든 케이스를 탐색하는 부분
	for (int i = index; i < N; i++)
	{
		visited[i] = true;
		DFS(arr, visited, i + 1, N, count + 1, min);
		visited[i] = false;
	}
}

 

케이스를 탐색하는 부분은 이정도 뿐으로 위의 N과 M 문제와 다를 것이 없다.

스타트 팀, 링크 팀 모두를 생각할 필요는 없다.

스타트 팀에 들어 갈 사람들의 인덱스만 true로 설정해주면 되는 일.

링크팀 = 스타트 팀이 아닌 사람들.

 

	if (count == N/2)
	{
		int sum1 = 0, sum2 = 0;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (visited[i] && visited[j])
					sum1 += arr[i][j];
				else if (!visited[i] && !visited[j])
					sum2 += arr[i][j];
			}
		}
		int distance = abs(sum1 - sum2);
		if (*min > distance)
			*min = distance;

		return;
	}

 

이렇게 보면 위의 if문에 들어갈 코드는 간단하다.

 

for 문을 2중으로 돌리며

i, j 둘 다 true(스타트 팀) 이라면 스타트 팀 전력에 더해주고

i, j 둘 다 false(링크 팀) 이라면 링크 팀 전력에 더해준다.

 

그리고 두 전력의 차가 현재 최솟값보다 작은지를 비교해주면 끝이다.

 

 

전체 코드

#include <iostream>

using namespace std;

void DFS(int** arr, bool visited[], int index, int N, int count, int* min);

int main()
{
	int N;
	cin >> N;

	int** S = new int*[N];
	bool* visited = new bool[N];
	for (int i = 0; i < N; i++)
	{
		S[i] = new int[N];
		visited[i] = false;
	}

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

	int min = 40000;
	DFS(S, visited, 0, N, 0, &min);

	cout << min;

	for (int i = 0; i < N; i++)
	{
		delete[] S[i];
	}
	delete[] S;
	delete[] visited;
	return 0;
}

void DFS(int** arr, bool visited[], int index, int N, int count, int* min)
{
	if (count == N/2)
	{
		int sum1 = 0, sum2 = 0;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (visited[i] && visited[j])
				{
					sum1 += arr[i][j];
				}
				else if (!visited[i] && !visited[j])
				{
					sum2 += arr[i][j];
				}
			}
		}
		int distance = abs(sum1 - sum2);
		if (*min > distance)
			*min = distance;

		return;
	}

	for (int i = index; i < N; i++)
	{
		visited[i] = true;
		DFS(arr, visited, i + 1, N, count + 1, min);
		visited[i] = false;
	}
}