[알고리즘] 백준 14889번: 스타트와 링크 (C++), 복합형 문제, 백트래킹의 pruning

이번 문제는 처음으로 겪어보는 복합형(?) 문제였다.

여러 고난이 있었는데 고난을 겪었던 코드들을 읽어보면서 어떻게 정답에 도달했는지 알아보자.

---

논리를 어떻게 접근할까 (첫 번째 고난)

스타트팀 링크팀을 각각 나눠서 능력치를 더하고 비교해서 최솟값을 어떻게 구할지 논리에서 막혔었다.

1시간 정도 고민하다가 문제들을 분할시켜보았다.

 

1. 스타트 팀, 링크 팀 나누기

2. 각 팀 능력치 더하기

3. 각 팀 능력치의 차 값 구하기

4. 차 값의 최솟값 구하기

 

4개 정도로 분할시켜 하나씩 진행할 수 있었다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
bool visited[2001] = { 0, };
bool visited2[1001] = { 0, };
vector<int> answerArr;

int solution2(vector<int> num1, vector<int> num2, vector<vector<int>> arr) { // 각 항들 더하고 차 찾기
	int answer = 0;
	int sum1 = 0;
	int sum2 = 0;
	for (int i = 0; i < num1.size(); i++) {
		for (int j = 0; j < num1.size(); j++) {
			if (i == j) { // arr[1][1] 같은 사례는 없어야 함
				continue;
			}
			sum1 += arr[num1[i]][num1[j]];
		}
	}

	for (int i = 0; i < num2.size(); i++) {
		for (int j = 0; j < num2.size(); j++) {
			if (i == j) { // arr[1][1] 같은 사례는 없어야 함
				continue;
			}
			sum2 += arr[num2[i]][num2[j]];
		}
	}


	if (sum1 < sum2) {
		answer = sum2 - sum1;
	}
	else {
		answer = sum1 - sum2;
	}

	return answer;
}

void solution(int n, int cnt, vector<vector<int>> arr) { // 백트래킹
	if (cnt == n / 2) {
		vector<int> num1;
		vector<int> num2;
		for (int i = 1; i <= n; i++) {
			if (visited[i] == 1) {
				//cout << i << ' ';
				num1.push_back(i);
			}
		}
		//cout << '\n';
		for (int i = 1; i <= n; i++) {
			if (visited[i] == 0) {
				//cout << i << ' ';
				num2.push_back(i);
			}
		}
		//cout << '\n';
		answerArr.push_back(solution2(num1, num2, arr));
		return;
	}

	for (int i = 1; i <= n; i++) {
		if (!visited[i]) {
			visited[i] = true;
			solution(n, cnt + 1, arr);
			visited[i] = false;
		}
	}
}

int main() {
	cin >> n;
	vector<vector<int>> arr(n + 1, vector<int>(n + 1, 0));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int a;
			cin >> a;
			arr[i][j] = a;
		}
	}

	solution(n, 0, arr);

	sort(answerArr.begin(), answerArr.end());
	cout << answerArr[0];

	return 0;
}

[입력]

1. 우선 입력을 받기 위해 main에서 2차원 배열을 선언하여 입력을 받았다. 아무래도 vector형이 아니었다면 전역으로 선언했을 텐데 vector는 어떻게 전역으로 선언할지 몰라서 조금 어리석은 방법이지만 main에서 선언하여 모든 함수에 파라미터로 넣고 계속 끌고 갔다.

 

[팀 나누기 (여러 경우의 수)] (함수: solution1)

2. cnt를 파라미터로 넣어서 입력받은 n의 반이 되면 팀 나누기가 되었다고 처리하고, 다음 과정을 실행시킨다. 그리고, 팀을 나누는 과정에서 백트래킹을 했었다고 생각했는데 이는 나중에 시간 초과 문제를 일으킨다. 팀을 나누고 각각 num1, num2 배열에 넣어주었다.

 

[각 팀 능력치 더 하기, 능력치의 차 구하기] (함수: solution2)

다음 과정은 생각보다 간단하다. 2중 for문을 사용했는데 예를 들어 arr[3][3]과 같이 똑같은 위치에 있는 배열의 원소를 더하지 않는다는 조건만 걸어주면 쉽게 sum을 구해서 차를 구할 수 있었다.

 

[최솟값 구하기]

모든 최솟값들의 경우의 수들을 answerArr에 넣어주고, 정렬을 시켜 맨 앞에 있는 원소(최솟값)를 출력했다.

---

시간 초과 (두 번째 고난)

이상하게 TC는 다 통과하는데 TLE가 났었다.

게시판에 있던 반례 중에 다음을 실행해보았다.

https://www.acmicpc.net/board/view/50632

글 읽기 - 데이터를 추가해 주세요

output이 1인 건 잘 나오지만 시간이 거의 1분 걸렸었던 거 같다.

아무래도 논리들을 짜고, 코드로 작성하는 데에 있어서 백트래킹의 pruning이 잘 되지 않았던 거 같았다.

 

기존의 백트래킹은 아예 완전 탐색이었었다. 그래서 파라미터에 idx를 하나 더 걸어주며 탐색의 경우를 더 줄일 수 있었다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
bool visited[2001] = { 0, };
bool visited2[1001] = { 0, };
vector<int> answerArr;

int solution2(vector<int> num1, vector<int> num2, vector<vector<int>> arr) { // 각 항들 더하고 차 찾기
	int answer = 0;
	int sum1 = 0;
	int sum2 = 0;
	for (int i = 0; i < num1.size(); i++) {
		for (int j = 0; j < num1.size(); j++) {
			if (i == j) { // arr[1][1] 같은 사례는 없어야 함
				continue;
			}
			sum1 += arr[num1[i]][num1[j]];
		}
	}

	for (int i = 0; i < num2.size(); i++) {
		for (int j = 0; j < num2.size(); j++) {
			if (i == j) { // arr[1][1] 같은 사례는 없어야 함
				continue;
			}
			sum2 += arr[num2[i]][num2[j]];
		}
	}


	if (sum1 < sum2) {
		answer = sum2 - sum1;
	}
	else {
		answer = sum1 - sum2;
	}

	return answer;
}

void solution(int n, int idx, int cnt, vector<vector<int>> arr) { // 백트래킹
	if (cnt == n / 2) {
		vector<int> num1;
		vector<int> num2;
		for (int i = 1; i <= n; i++) {
			if (visited[i] == 1) {
				//cout << i << ' ';
				num1.push_back(i);
			}
		}
		//cout << '\n';
		for (int i = 1; i <= n; i++) {
			if (visited[i] == 0) {
				//cout << i << ' ';
				num2.push_back(i);
			}
		}
		//cout << '\n';
		answerArr.push_back(solution2(num1, num2, arr));
		return;
	}

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

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

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

	solution(n, 0, 0, arr);

	sort(answerArr.begin(), answerArr.end());
	cout << answerArr[0];

	return 0;
}

 

하지만, 14%까지 밖에 통과를 못 했다.

---

잘못된 매개변수 (3번째 고난)

그래서 논리의 오류일까 싶어 노트에 도식화를 해보던 중 분명히 시작은 1부터 하는데 main에서 idx 자리에 무의식적으로 0을 넣어둔 것을 알 수 있었다.

 

이를 1로 고쳐주었다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
bool visited[21] = { 0, };
vector<int> answerArr;

int solution2(vector<int> num1, vector<int> num2, vector<vector<int>> arr) { // 각 항들 더하고 차 찾기
	int answer = 0;
	int sum1 = 0;
	int sum2 = 0;
	for (int i = 0; i < num1.size(); i++) {
		for (int j = 0; j < num1.size(); j++) {
			if (i == j) { // arr[1][1] 같은 사례는 없어야 함
				continue;
			}
			sum1 += arr[num1[i]][num1[j]];
		}
	}

	for (int i = 0; i < num2.size(); i++) {
		for (int j = 0; j < num2.size(); j++) {
			if (i == j) { // arr[1][1] 같은 사례는 없어야 함
				continue;
			}
			sum2 += arr[num2[i]][num2[j]];
		}
	}


	if (sum1 < sum2) {
		answer = sum2 - sum1;
	}
	else {
		answer = sum1 - sum2;
	}

	return answer;
}

void solution(int n, int idx, int cnt, vector<vector<int>> arr) { // 백트래킹
	if (cnt == n / 2) {
		vector<int> num1;
		vector<int> num2;
		for (int i = 1; i <= n; i++) {
			if (visited[i] == 1) {
				//cout << i << ' ';
				num1.push_back(i);
			}
		}
		//cout << '\n';
		for (int i = 1; i <= n; i++) {
			if (visited[i] == 0) {
				//cout << i << ' ';
				num2.push_back(i);
			}
		}
		//cout << '\n';
		answerArr.push_back(solution2(num1, num2, arr));
		return;
	}

	for (int i = idx; i <= n; i++) {
		// visited는 1, 1, 1, ... 같은 중복 방지
		// i + 1인 이유는 굳이 visit되어 있는 곳을 안 가도 될 거 같아서..??
		if (!visited[i]) {
			visited[i] = true;
			solution(n, i + 1, cnt + 1, arr);
			visited[i] = false;
		}
	}
}

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

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

	solution(n, 1, 0, arr);

	sort(answerArr.begin(), answerArr.end());
	cout << answerArr[0];

	return 0;
}

---

느낀 점

문제를 분할 형식으로 생각할 수 있어야 한다.

백트래킹의 pruning을 잘 확인해야 한다.