#15661번 링크와 스타트 (C++)

문제 링크 : www.acmicpc.net/problem/15661

15661번: 링크와 스타트

문제 풀이는 다음과 같다.

(1) 전형적인 DFS문제로, A팀과 B팀으로 나뉘는 조합을 DFS로 구한다.

(1)-(2) 즉, bool문을 만들어 1번과 2번이 같은 팀이면 두 번호를 true로, 3번과 4번이 같은 팀이면 자동적으로 남은 사람들은 false로 구성해준다. 

(2) 그렇게 true끼리 묶인 사람끼리의 합과 false끼리 묶인 사람들의 합의 절대값의 차이를 구해서 작은값과 비교해 저장해 나간다.

 

#include <iostream>
#include <climits>
#include <cmath>
using namespace std;

int n = 0, arr[21][21] = {0,}, ans = INT_MAX;
bool ch[21] = {false,};

void dfs(int st){
    if(st>=n){
        int st = 0, lin = 0;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(ch[i]&&ch[j]) st+=arr[i][j];
                else if(!ch[i]&&!ch[j]) lin+=arr[i][j];
            }
        }
        if(ans>abs(st-lin)) ans = abs(st-lin);
    }
    for(int i=st; i<=n; i++){
        if(!ch[i]){
            ch[i] = true;
            dfs(i);
            ch[i] = false;
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> arr[i][j];
        }
    }
    dfs(1);
    cout << ans << "\n";
    return 0;
}

예전에 백준 세컨드 아이디로 풀어본 적이 있었던 문제였다.

시간도 훨씬 단축되는 방식으로 풀었지만, 스스로 온전히 터득한게 아닌 남의 해설을 보고 거의 외운거나 다름이 없는 답안이었다.

만약 실전에서 나온다면 그 긴장되는 상황속에서 '내 머리에서 순수하게 나온 아이디어'로 최단시간에 풀어서 남에게 해설할 수 있는 답을 내놓아 보자, 라는 마음으로 다시 한번 풀어보았다.