BOJ 14889 : 스타트와 링크

#BOJ 14889 : 스타트와 링크

14889번: 스타트와 링크

#풀이

 

문제에서 예시로 보여주는 인접행렬형태를 보고 그래프문제인가 싶었지만 차근차근 읽어보니 백트래킹 문제였다.

 

조합을 사용하여 풀면 간단하게 풀 수 있는 문제이다.

 

#코드

#include<bits/stdc++.h>

using namespace std;
int n;
int arr[21][21];
int min_ans = 0x7f7f7f7f;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	
	for(int i = 1; i <=n; i++){
		for(int j = 1; j <=n; j++){
			cin >> arr[i][j];
		}
	}
	
	
	int back[21];
	for(int i = 1; i <=n; i++){
		if(i <= n/2)
			back[i] = 0;
		else
			back[i] = 1;
	}
	
	do{
		int ans = 0;
		vector<int> v_1;
		vector<int> v_2;
		for(int i = 1; i <=n; i++){
			if(back[i] == 1)
				v_1.push_back(i);
			else
				v_2.push_back(i);
		}
		
		for(int i = 0; i < v_1.size(); i++){
			for(int j = 0; j < v_1.size(); j++){
				ans+= arr[v_1[i]][v_1[j]];
			}
		}
		for(int i = 0; i < v_2.size(); i++){
			for(int j = 0; j < v_2.size(); j++){
				ans-= arr[v_2[i]][v_2[j]];
			}
		}
		ans = ans < 0 ? ans *-1: ans;
		if(min_ans > ans)
			min_ans = ans;
	
	}while(next_permutation(back+1, back+1+n));
	cout << min_ans<<'\n';
	return 0;
}