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

문제

참조블로그

📝 문제풀이

모든 경우의 수를 비교해봐야 하는 문제입니다.
따라서 완전탐색이라고 생각했습니다!

그리고 맞나 싶어서 분류를 봤더니!!
허거덩.... 바로 dfs,백트래킹 문제였습니다!

dfs, 백트래킹 문제 유형
해가 아니라면 다시 돌아온다 라는 내용이 있으면 이 부분이 가지치기 라고 합니다.
불필요한 경로는 굳이 끝까지 탐색하지 않겠다는 의미입니다.
해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아갑니다.
대표적인 문제로는 'N-Queen','배낭문제','순열/조합' 등의 유형들이 있다고 합니다.

그래서 저희 문제에서도 이와 같이 생각해보면,

팀의 명수가 N/2와 동일해야 합니다. 이 경우가 아닐경우는 굳이 탐색하지 않아도 됩니다.
그래서 가지치기 조건을 N/2와 동일할 때로 설정하면 됩니다.

만일 조건을 걸지않고 단순히 DFS 를 한다면 1명과 3명의 조합 뭐 이런식의 경우도 다 탐색을 하게 되므로 비효율적입니다!

✏️ 결과코드

#include <iostream>
#include <math.h>
#include <limits.h>
using namespace std;

int N;
int map[20][20];
bool visited[20];
int ans = INT_MAX;

void dfs(int cnt,int pos){

    if(cnt == N/2){

        int start=0;
        int link=0;

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(visited[i]==true && visited[j]==true) start += map[j][i];
                if(visited[i]==false && visited[j]==false) link += map[j][i];
            }
        }

        int temp = abs(start - link);
        if(ans > temp) ans = temp;
        
    }

    for(int a=pos;a<N;a++){
        visited[a]=true;
        dfs(cnt+1,a+1);
        visited[a]=false;
    }
    
}

int main(){

    cin >> N;

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

    dfs(0,0);

    cout << ans;
    
}