[백준 15661번 C++] 링크와 스타트

 

[백준 15661번 C++] 링크와 스타트

 

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

---

 

 

해결전략

비트마스킹 Bitmasking
백트래킹 Backtracking

---

 

정답코드 - 비트 마스킹

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n; // 팀의 인원 수
int answer = 987654321;
vector<vector<int>> v;

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

	cin >> n;
	v.resize(n, vector<int>(n));
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			cin >> v[y][x];
		}
	}

	// 모든 가능한 팀 조합을 비트마스크로 생성
	for (unsigned int bitmask = 0; bitmask < (1 << n); bitmask++)
	{
		vector<int> teamStart, teamLink; // 두 팀을 저장

		// 비트마스크를 통해 팀을 나누는 과정
		for (int i = 0; i < n; i++)
		{
			if (bitmask & (1 << i)) {
				teamStart.push_back(i);
			}
			else {
				teamLink.push_back(i);
			}
		}
		//sort(teamStart.begin(), teamStart.end());
		//sort(teamLink.begin(), teamLink.end());

		
		// 각 팀의 능력치 합 계산
		int sumStart = 0, sumLink = 0;
		for (int i = 0; i < teamStart.size(); i++){
			for (int j = 0; j < teamStart.size(); j++)
			{
				sumStart += v[teamStart[i]][teamStart[j]];
			}
		}

		for (int i = 0; i < teamLink.size(); i++) {
			for (int j = 0; j < teamLink.size(); j++)
			{
				sumLink += v[teamLink[i]][teamLink[j]];
			}
		}

		answer = min(answer, abs(sumStart - sumLink));
	}

	cout << answer;

	return 0;
}

 

---

 

 

정답코드 - 백트래킹, 재귀

 

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int n; // 팀의 인원 수
int answer = 987654321;
vector<vector<int>> v;
vector<bool> ch; 		// 각 인원이 어떤 팀에 속하는지 표시하는 벡터

// 팀의 능력치 합을 계산하는 함수
int calculateTeamScore(const vector<int>& teamMembers) 
{
    int score = 0;
    for (int i = 0; i < teamMembers.size(); ++i) {
        for (int j = 0; j < teamMembers.size(); ++j) {
            score += v[teamMembers[i]][teamMembers[j]];
        }
    }
    return score;
}

// 백트래킹을 이용하여 모든 팀 구성을 탐색하는 함수
void backtrack(int idx, int count) 
{
    if (idx == n) {
        if (count == 0 || count == n) return; // 한 팀이 비어있는 경우는 무시

        vector<int> teamStart, teamLink;
        for (int i = 0; i < n; ++i) {
            if (ch[i]) {
                teamStart.push_back(i);
            } else {
                teamLink.push_back(i);
            }
        }

        // 각 팀의 능력치 합 계산
        int sumStart = calculateTeamScore(teamStart);
        int sumLink = calculateTeamScore(teamLink);

        // 두 팀의 능력치 차이의 절대값을 계산하여 최소값 업데이트
        answer = min(answer, abs(sumStart - sumLink));
        return;
    }

    // 현재 인원을 teamStart에 추가하는 경우
    ch[idx] = true;
    backtrack(idx + 1, count + 1);

    // 현재 인원을 teamLink에 추가하는 경우
    ch[idx] = false;
    backtrack(idx + 1, count);
}

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

    cin >> n;
    v.resize(n, vector<int>(n));
    ch.resize(n);
    
    for (int y = 0; y < n; ++y) {
        for (int x = 0; x < n; ++x) {
            cin >> v[y][x];
        }
    }

    backtrack(0, 0); // 백트래킹 시작

    cout << answer;

    return 0;
}

 

---