침대 밖은 위험해!

#include<iostream>
using namespace std;

int n, s[21][21], teamA[21], teamB[21], ans = 987654321;

int abs(int a){
	return ((a < 0) ? -a : a);
}

int calScore(int team[21]){
	int temp = 0;
	for (int i = 0; i < n / 2 - 1; i++){
		for (int j = i + 1; j < n / 2; j++){
			temp += s[team[i]][team[j]] + s[team[j]][team[i]];
		}
	}
	return temp;
}

void dfs(int num, int cnt_a, int cnt_b){
	if (cnt_a == n / 2 && cnt_b == n / 2){
		int score_a = calScore(teamA);
		int score_b = calScore(teamB);
		if (abs(score_a - score_b) < ans)
			ans = abs(score_a - score_b);
		return;
	}

	// teamA
	if (cnt_a < n / 2){
		teamA[cnt_a] = num;
		dfs(num + 1, cnt_a + 1, cnt_b);
	}
	// teamB
	if (cnt_b < n / 2){
		teamB[cnt_b] = num;
		dfs(num + 1, cnt_a, cnt_b + 1);
	}
}

int main(void){
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> s[i][j];

	dfs(1, 0, 0);
	cout << ans << "\n";
	return 0;
}

#include<iostream>
#include<queue>
using namespace std;

int n, map[101][101], dist[101][101], ans = 987654321;
int dr[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, -1, 0, 1 };
queue<pair<int, int> > q;

void dfs(int r, int c, int cnt){
	dist[r][c] = 1;
	map[r][c] = cnt;
	q.push(make_pair(r, c));

	for (int k = 0; k < 4; k++){
		int nr = r + dr[k];
		int nc = c + dc[k];

		if (0 <= nr && nr < n && 0 <= nc && nc < n && dist[nr][nc] == 0 && map[nr][nc] == 1){
			dfs(nr, nc, cnt);
		}
	}
}

int main(void){
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];

	int cnt = 1;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (dist[i][j] == 0 && map[i][j] == 1)
				dfs(i, j, cnt++);

	while (!q.empty()){
		int r = q.front().first;
		int c = q.front().second;
		q.pop();

		for (int k = 0; k < 4; k++){
			int nr = r + dr[k];
			int nc = c + dc[k];

			if (0 <= nr && nr < n && 0 <= nc && nc < n){
				if (map[nr][nc] == 0){
					q.push(make_pair(nr, nc));
					map[nr][nc] = map[r][c];
					dist[nr][nc] = dist[r][c] + 1;
				}
				else if (map[nr][nc] != map[r][c] && dist[r][c] + dist[nr][nc] - 2 < ans){
					ans = dist[r][c] + dist[nr][nc] - 2;
				}
			}
		}
	}

	cout << ans << "\n";
	return 0;
}

#include<iostream>
#include<queue>
using namespace std;

int n, m, ans;
char map[101][101];
int dr[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, -1, 0, 1 };

int main(void){
	cin >> n >> m;
	for (int i = 0; i < n; i++){
		cin >> map[i];
	}

	queue<pair<pair<int, int>, int> *gt; q;
	q.push(make_pair(make_pair(0, 0), 1));
	map[0][0] = '0';

	while (!q.empty()){
		int r = q.front().first.first;
		int c = q.front().first.second;
		int cnt = q.front().second;
		q.pop();

		if (r == n - 1 && c == m - 1){
			ans = cnt;
			break;
		}

		for (int k = 0; k < 4; k++){
			int nr = r + dr[k];
			int nc = c + dc[k];

			if (0 <= nr && nr < n && 0 <= nc && nc < m && map[nr][nc] == '1'){
				q.push(make_pair(make_pair(nr, nc), cnt + 1));
				map[nr][nc] = '0';
			}
		}
	}

	cout << ans << "\n";
	return 0;
}