백준 14889 스타트와 링크 / C++

문제 : 14889

풀이 point

백트래킹의 대명사 N과 M문제를 풀어봤다면 그 문제의 코드를 약간씩 변형해서 풀면 될것 같다는 생각이 들테다.

풀이 방법

백트래킹을 활용하는 문제이다.
스타트 팀에서 선택한 숫자는 링크 팀에서는 선택할 수 없다.
스타트 팀에서 먼저 숫자를 고른 후 visit배열에 저장한뒤 링크 팀에서는 스타트 팀이 고른 숫자를 제외한 나머지 숫자들을 선택한다.

선택한 후 숫자를 더하고 빼서 차이를 최소화 한다.
중복과 이미 선택한 숫자는 숫자를 고를 때 배제한다.(ex 12 21 or 11 )

코드

//백준 14889, 스타트와 링크

#include <iostream>
#include <vector>
#include <climits>

int N;
int grid[21][21];
int visit[21];
std::vector<int> start;
std::vector<int> link;
int min{INT_MAX};

void solve(int k, int st){
    if(k == N/2){
        int sum{0};
        for(int i{0}; i<N; ++i){
            if(visit[i]) start.push_back(i);
            else link.push_back(i);
        }
        for(int i{0}; i<N/2; ++i){
            for(int j{i+1}; j<N/2; ++j){
                sum += grid[start[i]][start[j]] + grid[start[j]][start[i]];
                sum -= grid[link[i]][link[j]] + grid[link[j]][link[i]];
            }
        }
        min = std::min(min, std::abs(sum));
        start.clear();
        link.clear();
        return;
    }

    for(int i{st}; i<N; ++i){
        if(visit[i]) continue;
        visit[i] = true;
        solve(k+1, i+1);
        visit[i] = false;
    }
}

int main (){

    std::cin >> N;
    for(int i{0}; i<N; ++i){
        for(int j{0}; j<N; ++j){
            std::cin >> grid[i][j];
        }
    }
    solve(0, 0);
    std::cout << min;

    return 0;
}