Problem
Concept & Idea
간단한 완전탐색 문제였다. n도 최대 20밖에 안되서 dfs로 쉽게 해결할 수 있었다. 코드도 나름 깔끔하게 짰다고 생각하는데,, startScore랑 linkScore를 어떻게 하면 함수를 합칠 수 있을것 같은데,, 나름 만족한다.
Code
#include <iostream>
#include <vector>
using namespace std;
int n,map[21][21];
bool check[21];
int res=2000001;
int startScore(vector<int> start){
int cnt=0;
for(int i=0; i<start.size(); i++) {
for(int j=i+1; j<start.size(); j++) {
cnt+=map[start[i]][start[j]]+map[start[j]][start[i]];
}
}
return cnt;
}
int linkScore(){
int cnt=0;
vector<int> link;
for(int i=1; i<=n; i++) {
if(!check[i])
link.push_back(i);
}
for(int i=0; i<link.size(); i++) {
for(int j=i+1; j<link.size(); j++) {
cnt+=map[link[i]][link[j]]+map[link[j]][link[i]];
}
}
return cnt;
}
void dfs(int x, vector<int> start){
if(start.size()==n/2) {
int sta=startScore(start);
int lin=linkScore();
res=min(res,abs(sta-lin));
} else {
for(int i=x+1; i<=n; i++) {
check[i]=true;
start.push_back(i);
dfs(i,start);
start.pop_back();
check[i]=false;
}
}
}
int main(){
cin>>n;
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++)
cin>>map[i][j];
}
vector<int> temp;
dfs(0,temp);
cout<<res<<endl;
}
Fealing
간단한 완전탐색 문제였다. 간단해서 리뷰를 쓰지않아도 되긴 하지만,, 그냥 코드를 잘 짠것같아서 올려보았다. 문제를 보고 겁만 안내면 좋을 것 같은데,, 겁을 내서 문제다 😢
Check out this code in Victoria’s Gist. Please Comment my code in this link.