[백준][C++] 스타트와 링크 (246)

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

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

14889번: 스타트와 링크

이번 문제는 백트래킹 알고리즘의 대표적인 문제라 생각되어 정리해본다.

 

생각의 흐름

우선 vec1, vec2 각각에 모든 사람의 번호를 집어넣어서 가능한 모든 케이스를 구하되 애당초 불가능 경우 바로 return 하면 됩니다.

이게 무슨 의미일까요? 불가능 경우란 어떤 상황일까요?

 

예를 들어 1번부터 8번 까지의 사람이 있다고 해봅시다.

	1	2	3	4	5	6	7	8
vec1	o		o	o	o	o
vec2		o

위와 같이 6번 사람을 vec1에 집어넣는 순간 vec1이 5명이 되어버리고, 이는 문제의 조건인 "각 팀의 수가 같아야 된다"는 조건을 위배하게 됩니다.

 

따라서 바로 return하여 해당 case에 대한 탐색을 중단하면 됩니다.

즉, 백트래킹을 사용하게 된 것 이죠!

 

함수의 의미는 다음과 같이 부여하였습니다.

go(int index, vector<int>& first, vector<int>& second);

index번째 사람을 어떤 팀에 넣을지 결정해야 하며, 1번팀과 2번팀에 속한 사람이 각각 first, second 벡터 안에 들어있습니다.

 

재귀적 탐색을 하며,

 

1) 정답을 찾은 경우

index == n인 경우, 모든 사람을 분배했다는 것 입니다. 따라서 결과 계산을 수행

 

2) 불가능한 경우

first의 크기 > N/2;

second의 크기 > N/2;

 

3) 다음 경우

vec1.push_back(index);
go(index + 1, vec1, vec2);
vec1.pop_back();

vec2.push_back(index);
go(index + 1, vec1, vec2);
vec2.pop_back();

 

 

나의 코드

#include <bits/stdc++.h>

using namespace std;

int N;
int MAP[21][21];
int res = 2147000000;

void go(int index, vector<int>& vec1, vector<int>& vec2) {
    if(index == N) {
        if(vec1.size() != N/2) return;
        if(vec2.size() != N/2) return;

        int t1 = 0, t2 = 0;

        for(int i = 0; i < N/2; i++) {
            for(int j = 0; j < N/2; j++) {
                if(i == j) continue;
                t1 += MAP[vec1[i]][vec1[j]];
                t2 += MAP[vec2[i]][vec2[j]];
            }
        }

        res = min(res, abs(t1 - t2));
    } else if(vec1.size() > N/2 || vec2.size() > N/2) {
        return;
    } else {
        vec1.push_back(index);
        go(index + 1, vec1, vec2);
        vec1.pop_back();

        vec2.push_back(index);
        go(index + 1, vec1, vec2);
        vec2.pop_back();
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

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

    vector<int> vec1, vec2;
    go(0, vec1, vec2);
    cout << res;

    return 0;
}