백준(BOJ) 그래프 순회 - 스타트와 링크 (14889) - Silver 2

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

14889번: 스타트와 링크

문제

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

i\j12341234

	1	2	3
4		5	6
7	1		2
3	4	5

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S12 + S21 = 1 + 4 = 5
• 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S13 + S31 = 2 + 7 = 9
• 링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

입력

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

문제 해결

해당 문제를 보고 여러 알고리즘을 떠올렸지만 N이 20으로 그렇게 높은 시간복잡도를 요구하지 않는다는걸 느껴서 모든 경우의수를 탐색하는 백트랙킹 방식을 생각했다. 백트래킹(Backtracking)은 조합적 문제나 순열 문제와 같은 여러 가능한 해를 찾는 문제를 해결하기 위한 알고리즘 기법이다. 이 알고리즘은 가능한 모든 후보해를 시도하다가 조건을 만족하지 않으면 이전 단계로 돌아가서 다른 후보해를 시도하는 방식으로 작동한다. 백트래킹은 모든 가능성을 조사하지만, 불필요한 조사를 줄여 최적화할 수 있는 경우도 있다. 해당문제에서는 1번 선수와 2번 선수를 탐색한 경우 (1, 2) 2번 선수와 1번 선수를 다시 탐색할 필요가 없다.(1, 2) == (2, 1) 이 부분을 놓치면 시간초과에 빠질 수 있고 실제로 이 부분을 놓쳐 5번정도 시간초과에 빠졌다... 일단 접근 방식은 다음과 같다.

 

1. 백트랙킹을 이용하여 1번선수부터 N/2명의 선수들을 teamA에 합류 시킨후 마지막으로 teamA에 들어간 선수를 빼준다.

for(ll i=index; i<startNlink.size(); i++){
	teamA.push_back(i); // teamA에 선수 1명 영입
	backtracking(startNlink, i+1,  cnt-1); //위 선수를 제외한 다음 선수 탐색 시작
	teamA.pop_back(); // 영입했던 마지막 선수 제외
}

## 여기서 반복문에서 i = index로 해서 이미 계산된 경우의 수는 제외해야한다 (1, 2) == (2, 1)

for(ll i=1; i<startNlink.size(); i++){
// 기존 i를 1부터 돌린 경우 시간초과를 피할 수 없다... 실수 조심
	teamA.push_back(i);
	backtracking(startNlink, cnt+1);
	teamA.pop_back();
}

2. teamA에 합류하지 못한 선수들은 모두 teamB에 합류시킨다.

for(ll i=1; i<startNlink.size(); i++){ // 모든 선수명단을 체크
	it = find(teamA.begin(), teamA.end(), i); 
		if(it == teamA.end()){ //만약 teamA에 속하지 못한 선수가 있는 경우
			teamB.push_back(i); // teamB에 영입
	}
}

3. 각각 팀별 능력치의 합을 구한 후 최솟값 갱신을 한다.

for(ll i=0; i<teamA.size()-1; i++){
	for(ll j=i+1; j<teamA.size(); j++ ){
		sumA += startNlink[teamA[i]][teamA[j]];
		sumA += startNlink[teamA[j]][teamA[i]]; //A팀 시너지 계산

		sumB += startNlink[teamB[i]][teamB[j]];
		sumB += startNlink[teamB[j]][teamB[i]]; //B팀 시너지 계산
	}
}

if (minValue > abs(sumA - sumB)) // 최솟값 갱신
	minValue = abs(sumA - sumB);

4. teamB의 인원을 초기화 시킨다.

teamB.clear(); // B팀 초기화
return ;

위 과정을 통해 TeamA와 TeamB의 명단을 구할 수 있다.

 

5. 최종 minValue 출력

cout << minValue << "\n";

전체코드

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 2147483647

using namespace std;
typedef long long ll;

vector<ll>teamA;
vector<ll>teamB;
ll minValue = INF;

void backtracking(vector<vector<ll> >&startNlink,ll index, ll cnt){
    vector<ll>::iterator it;

    if(cnt== 0){
        for(ll i=1; i<startNlink.size(); i++){ // 모든 선수명단을 체크
	        it = find(teamA.begin(), teamA.end(), i); 
		        if(it == teamA.end()){ //만약 teamA에 속하지 못한 선수가 있는 경우
			        teamB.push_back(i); // teamB에 영입
	            }
        }

        ll sumA = 0;
        ll sumB = 0;
        
        for(ll i=0; i<teamA.size()-1; i++){
            for(ll j=i+1; j<teamA.size(); j++ ){
                sumA += startNlink[teamA[i]][teamA[j]];
                sumA += startNlink[teamA[j]][teamA[i]]; //A팀 시너지 계산

                sumB += startNlink[teamB[i]][teamB[j]];
                sumB += startNlink[teamB[j]][teamB[i]]; //B팀 시너지 계산
            }
        }
    
        if (minValue > abs(sumA - sumB)) // 최솟값 갱신
            minValue = abs(sumA - sumB);
        teamB.clear(); // B팀 초기화
        return ;
    }
    else{
        for(ll i=index; i<startNlink.size(); i++){
            teamA.push_back(i); // teamA에 선수 1명 영입
            backtracking(startNlink, i+1,  cnt-1); //위 선수를 제외한 다음 선수 탐색 시작
            teamA.pop_back(); // 영입했던 마지막 선수 제외
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("input.txt", "r" ,stdin);

    ll N = 0;
    cin >> N;
    vector<vector<ll> >startNlink(N+1, vector<ll>(N+1, 0));
    vector<ll>visit(N+1, 0);

    for(ll i=1; i<=N; i++){
        for(ll j=1; j<=N; j++){
            cin >> startNlink[i][j];
        }
    }
    backtracking(startNlink, 1, N/2);
    cout << minValue << "\n";
    return 0;
}

머리로는 알겠지만 시간에 쫒겨 구현하려고 하니 뇌정지가 온다. 자주 연습해서 적응해야하는 알고리즘중 하나이다.