[ 백준 14889 ] 스타트와 링크 C/C++ DFS

# 문제링크

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

이것도 Depth 가 최대 10이라서 DFS로 팀을 나눠주고, 팀 배정에 따라 map 에서 계산만 해주면 되는 문제였다. 근데 (1, 2), (3, 4) 이나 (2, 1), (4, 3) 이나 같은 팀이다. 이걸 생각도 안해보고 구현만 바로 해서 제출하니 시간초과가 났다. 

 

테케 답은 맞게 나오니,, 원인도 제대로 모르고 괜히 배열 인덱스만 만져보다가 나중에 해당 원인을 알게 되었다. 그래서 중복 없는 조합으로 짜주었다. 물론 여기서도 (1, 2), (3, 4) 와 (3, 4), (1, 2) 가 겹친다는 한계점이 있긴 하지만 통과가 됐으니 다행이다..

 

# 제출 코드 

 

#include <cstdio>
using namespace std;
#define abs(x) ((x) < 0 ? -(x): (x))
int N;
int map[22][22];
bool chk[22];
int ans = 0x7fffffff;

void Calc() {
	int A, B;
	A = B = 0;
	for (int i = 1; i <= N; i++) {
		if (chk[i] == true) { // true 팀 더하기 
			for (int j = 1; j <= N; j++) {
				if (chk[j] == true)
					A += map[i][j];
			}
		}
		else { // false 팀 더하기 
			for (int j = 1; j <= N; j++) {
				if (chk[j] == false)
					B += map[i][j];
			}
		}
	}
	int tmp = abs(A - B);
	if (tmp < ans)ans = tmp;
}

void DFS(int node, int start) {
	if (node == N / 2) {
		Calc();
		return;
	}
	for (int i = start; i <= N; i++) {
		chk[i] = true;
		DFS(node + 1, i + 1);
		chk[i] = false;
	}
}

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	DFS(0, 1);
	printf("%d\n", ans);
}

 

 

 

 

시간ㄴ초과...