[백준 14889] 스타트와 링크 (C++) - S1

문제

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

14889번: 스타트와 링크

 

개요

문제를 읽자마자 백트래킹을 이용해겠다고 생각했다.

바로 이전에 백트래킹 문제를 한 번 풀어봤기 때문에 감을 살려서 도전했다.

그러나, 백트래킹 함수를 구현할수록 코드가 너무 과하게 복잡해지는 느낌이 들었고, 테스트케이스 실행 시 자꾸 다른 답이 도출되었다.

결구 이 문제 또한 구글링을 시도했다...! 

구글링한 후 코드를 참고하고 이해한 후에, 다시 내 식대로 코드를 작성했는데 테스트케이스 3가지는 모두 통과하는데, 제출하면 자꾸만 시간 초과가 떴다....

1시간 넘게 틀린 게 뭔지 찾았는데, func(cnt + 1, i + 1)이라고 써야 하는데 func(cnt + 1, idx + 1)이라고 썼던 것이 문제였다.

 

문제 풀이

백트래킹을 활용하는 문제이다.

 

총 n명이 존재하는데, 스타트 팀에 n / 2명, 링크 팀에 n / 2명 이렇게 중복 없이 팀이 이루어져야 한다.

중복 체크를 위해 visited 배열을 사용하였다.

visited[i] = 1이면 스타트 팀에, visited[i] = 0이면 링크 팀에 배정하였다.

그리고 이중 for문을 이용하여 팀에 포함된 스타트 팀, 링크 팀 각각의 팀원들의 능력치의 합을 구하였다. 

 

func 함수를 재귀적으로 사용하는 for문에서 idx를 사용하지 않고 i = 0부터 계속 for문을 돌리면 시간 초과가 뜨게 된다.

꼭 i = idx부터 시작하도록 해야 한다.

 

최종 결과값을 저장할 ans는 처음에 40000으로 초기화해주었다.

Sij는 100보다 작고, N <= 20이므로, 능력치의 전체 총합은 20 * 20 * 100 = 40000보다 작을 것이기 때문이다.

 

코드

#include <iostream>
#include <cstring>
#include <sstream>
#include <vector>
#include <deque>
#include <queue>
#include <map>
#include <algorithm>
#include <bitset>
#include <cmath>

using namespace std;

int n, ans = 40000;
int arr[20][20];
int visited[20];

void func(int cnt, int idx) {
	if (cnt == (n / 2)) {
		vector<int> start, link;
		int start_score = 0, link_score = 0;
		for (int i = 0; i < n; i++) {
			if (visited[i]) start.push_back(i);
			else link.push_back(i);
		}
		for (int i = 0; i < (n / 2); i++) {
			for (int j = 0; j < (n / 2); j++) {
				start_score += arr[start[i]][start[j]];
				link_score += arr[link[i]][link[j]];
			}
		}
		int temp = abs(start_score - link_score);
		ans = min(ans, temp);

		return;
	}

	for (int i = idx; i < n; i++) {
		visited[i] = 1;
		func(cnt + 1, i + 1);
		visited[i] = 0;
	}
}

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

	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}
	func(0, 0);
	cout << ans;
	return 0;
}

 

깨달은 점

백트래킹 함수를 구현하는 중간에 함수가 너무 복잡해지고 지저분해지면 뭔가 잘못된 것 같다는 의심을 할 필요가 있다는 생각이 들었다.

그리고 func 함수의 인자에 사용되는 idx를 for문의 범위에 사용하는 자연스러운 흐름에 익숙해져야겠다는 생각 또한 들었다.

연습만이 답인 것 같다.