[백준] 15661 - 링크와 스타

 

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

15661번: 링크와 스타트

개별적으로 비트마스킹 방식과 백트래킹 방식을 사용하여 풀었다.

아직 비트마스킹이 익숙하지 않아 생각하는데 오래 걸렸다.

 

1. 비트마스킹

알고리즘 방식

N = 4일 때,

4명의 학생을 조합을 통해 뽑을 수 있는 경우는 0과 2^4 - 1의 숫자가 비트에 저장되는 방식과 같다.

다시 말해 각 비트 자리수는 k번째 학생의 상태를 나타내고, 뽑히지 않은 경우 0, 뽑힌 경우 1라고 표현했다고하면,

0 0 0 0, 0 0 0 1, 0 0 1 0  ...

1 1 0 0, 1 0 1 0, 1 0 0 1 ...

1 1 1 0, 1 1 0 1 , 1 0 1 1 ...

1 1 1 1 와 같다. (총 16개 = 2^4)

 

이 때 1을 home팀, 2를 away팀으로 지정 후, 모든 경우에서 두 팀의 능력치의 차이를 구한 후 이 중 최소값을 출력한다.

 

소스코드

#include <iostream>
#include <cmath>
#include <vector>

//23 2 1 0 22 0 1 21 2 20

using namespace std;

int N;
int board[20][20];
int vis;
int answer = 0x7FFFFFFF;

int calculateStats(int vis) {
	int homeStats = 0;
	int awayStats = 0;
	for (int i = 0; i < N - 1; i++) {
		bool firstHomeTeam = (1 << i & vis) == 0 ? false : true;
		for (int j = i + 1; j < N; j++) {
			bool secondHomeTeam = (1 << j & vis) == 0 ? false : true;
			if (firstHomeTeam && secondHomeTeam) {
				awayStats += board[i][j] + board[j][i];
			}
			else if (!firstHomeTeam && !secondHomeTeam) {
				homeStats += board[i][j] + board[j][i];
			}
		}
	}
	return abs(homeStats - awayStats);
}

void bitMasking() {
	for (int i = 1; i < (1 << (N - 1)) - 1; i++) {
		answer = min(answer, calculateStats(i));
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
		}
	}

	bitMasking();

	cout << answer;
}

 

2. 백트래킹

알고리즘 방식

N = 4일 때,

home팀에 0명을 뽑을 경우, away팀은 4명,

home팀에 1명을 뽑을 경우, away팀은 자연스럽게 나머지 3명이된다. (2명, 3명, 4명도 동일)

home팀과 away팀을 구별하지 않으므로, home팀에서 3명을 뽑을 경우는 home팀에서 1명을 뽑을 경우와 중복된다.

따라서 home팀에서 N / 2명을 뽑을 경우까지만 조합을 구하고, 이 때 능력치 차이의 값 중 최소값을 출력한다.

 

소스코드

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int N;
int board[20][20];
bool vis[20];
int answer = 0x7FFFFFFF;

int calculateStats() {
	int homeStats = 0;
	int awayStats = 0;
	for (int i = 0; i < N - 1; i++) {
		for (int j = i + 1; j < N; j++) {
			if (!vis[i] && !vis[j]) {
				awayStats += board[i][j] + board[j][i];
			}
			else if (vis[i] && vis[j]) {
				homeStats += board[i][j] + board[j][i];
			}
		}
	}
	cout << abs(homeStats - awayStats) << ' ';
	return abs(homeStats - awayStats);
}

void dfs(int idx, int cnt) {
	if (cnt > N / 2)
		return;

	if (idx != 0)
		answer = min(calculateStats(), answer);

	for (int i = idx; i < N; i++) {
		vis[i] = true;
		dfs(i + 1, cnt + 1);
		vis[i] = false;
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
		}
	}

	dfs(0, 0);

	cout << answer;
}

 

1. 비트마스킹

2. 백트래킹