백트래킹 - 14889 스타트와 링크
이 문제는 DFS로 풀 수 있다
먼저 0 ~ N-1 의 index 중 N/2 길이의 조합을 탐색한다.
N = 4 일 때, 0, 1, 2, 3 중 길이 2의 순열은
(0, 1) (0, 2) (0, 3) (1, 2) (1, 3) (2, 3) ⇒ 총 6가지
만약 (0, 1)을 기준으로 계산한다고 가정하면,
s[0][1] + s[1][0] 과 s[2][3] + s[3][2] 의 차이를 계산해야 한다.
그렇다면 (2, 3)을 기준으로 계산했을 때와 중복되는 계산을 하게 된다.
떄문에 중복 계산을 막기 위해 (0, 1) (0, 2) (0, 3) 기준으로만 계산을 해야한다.
0, 1, 2, 3 부터 시작하여 모두 dfs를 실행한다면, 위 6가지의 순열이 모두 탐색되지만, 0부터 시작한 dfs만 실행하면 우리가 원하는 조합을 뽑을 수 있다.
m = n/2 길이의 조합을 뽑기 위해선 dfs에서 다음 탐색할 index 번호의 조건으로 (n-1-i) ≥ (m-1-depth) 를 주어야 한다.
•
n-1 : 숫자 배열의 마지막 index
•
i : 탐색할 번호의 index
•
n-1 - i : 탐색할 번호 다음에 남은 수들의 개수
•
m - 1 -depth : 현재 depth 다음 depth에서 앞으로 추가해야할 수들의 개수 (m = n/2)
arr에 m 길이의 원소가 추가되고 나면, 추가되지 않은 index들을 arr에 추가한 뒤, calculation을 호출하여 스타트팀(0 ~ m-1까지의 index)과 링크팀(m ~ N까지의 index)의 합의 차를 반환 받는다.
이 반환값을 ans와 비교하여, 더 작은 값을 ans에 저장하면 된다.
#include <iostream>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
int N;
int ans = 1000000000;
int s[21][21];
int arr[21];
bool visited[21] = { false, };
int calculation(int m) {
int sum1 = 0;
int sum2 = 0;
for (int i = 0; i < m; i++) {
int x = arr[i];
for (int j = 0; j < m; j++) {
if (i == j) continue;
int y = arr[j];
sum1 += s[x][y];
}
}
for (int i = m; i < N; i++) {
int x = arr[i];
for (int j = m; j < N; j++) {
if (i == j) continue;
int y = arr[j];
sum2 += s[x][y];
}
}
return abs(sum1 - sum2);
}
void dfs(int index, int depth) {
int m = n/2;
if (depth == m) {
for (int i = 0; i < N; i++) {
if (!visited[i])
arr[depth++] = i;
}
ans = min(ans, calculation(m));
return;
}
for (int i = index+1; i < N; i++) {
if (!visited[i] && (n - 1 - i) >= (m - 1 - depth)) {
visited[i] = true;
arr[depth] = i;
dfs(i, depth+1);
visited[i] = false;
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> s[i][j];
}
}
arr[0] = 0;
visited[0] = true;
dfs(0, 1);
cout << ans;
return 0;
}
C++
복사