#14889번 스타트와 링크 (c++)

백준 난이도별 문제 - 백트래킹의 최종문제.

그동안 풀었던 백트래킹 난이도별 문제에서 이것저것 개념을 영끌해서 풀어봤다. 

실제로 각 문제들의 일부 포인트들을 차용하면 개념은 쉽게 포착할 수 있었다.

 

처음 만든 코드는 모든 예제에서 정답이 나왔으나, 시간초과가 나와버렸다. 

/*
1. 전체 수의 1/2과, 1/2~2/2까지에 해당되는 2개의 랜덤 조합을 만든다 
2. 이 조합의 합산 값들의 최소값을 저장한다.
*/

#include <iostream>
#include <cmath>
#include <limits.h>
#include <vector> 
#define MAX 20
using namespace std;

int num = 0;
int temp1, temp2 = 0; //임시 비교값
int minval = INT_MAX;
int arr[MAX][MAX] = {0,};
bool check[MAX] = {false,};
vector <int> v;

void Stalink(int start, int count){
    if(count==num/2){
        for(int i=0; i<count; i++){
            for(int j=0; j<count; j++){
                temp1+=arr[v[i]][v[j]];
            }
        }
    }
    else if(count==num){
        for(int i=(num/2); i<count; i++){
            for(int j=(num/2); j<count; j++){
                temp2+=arr[v[i]][v[j]];
            }
        }
        if(abs(temp1-temp2)<minval) minval = abs(temp1-temp2);
        temp1 = 0; temp2 = 0;
        v.clear();
        return;
    }
    for(int i=0; i<num; i++){
        if(check[i]==false){
            check[i] = true;
            v.push_back(start);
            Stalink(start+1, count+1);
            check[i] = false;
        }
        else if(check[i]==true) continue; 
    }
}

void Input(){
    cin >> num; 
    for(int i=0; i<num; i++){
        for(int j=0; j<num; j++){
            cin >> arr[i][j];
        }
    }
}

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Input();
    Stalink(0, 1); 
    cout << minval;

    return 0; 
}

직관적으로는 이해되나, 어째 코드가 주렁주렁 긴데다가 2중 for문이 많아 비효율적이었다.

다른 방법을 고안해보기로 했다. 

 

우선적으로 수정했던 점은, Starlink의 재귀문인 for문에서

int i=0;이 아닌 i =start; 이었다. 

우린 순서만 바뀌거나  (1 3 2 -> 2 3 1)

혹은 중복된 숫자들의 조합은 신경 쓸 필요가 없다는 점을 상기해야한다. 

이 부분은 하단의 문제를 풀고넘어갔다면 이해할 수 있는 부분이다. 

https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

그리고 문득, 이중 for문이 너무 많다는 점을 고려하다가 

굳이 앞 뒤 두 부분(0~N/2미만과 N/2부터 N-1까지)을 구하지 않아도 되겠다는 생각이 들었다.

기껏 bool check[i]를 뒀는데, 이 bool문이 있으면 리소스를 낭비하지 않고 빠르게 계산할 수 있기 때문이다. 

#include <iostream>
#include <climits>
#define MAX 21
using namespace std;

int num = 0;
int minval = INT_MAX;
int arr[MAX][MAX];
int list1[10], list2[10];
bool check[MAX] = {false,};

int min(int a, int b) {return a<b? a:b;}

void Stalink(int start, int count){
    int x = 0;
    int temp1 = 0; int temp2 = 0; //임시 비교값
    if(count==num/2){
        for(int i=0; i<num; i++){
            if(!check[i]){list2[x] = i; x++;}
        }

        for(int j=0; j<num/2; j++){
            for(int k=0; k<num; k++){
                if(list1[j]!=k&&check[k]) temp1+=arr[list1[j]][k];
                if(list2[j]!=k&&!check[k]) temp2+=arr[list2[j]][k];
            }
        }
        minval = min(abs(temp1-temp2), minval);
        return;
    }
    for(int i=start; i<num; i++){ // i=1로 할 경우 시간초과가 나온다
        if(!check[i]){
            check[i] = true;
            list1[count] = i;
            Stalink(i+1, count+1);
            check[i] = false;
        }
    }
}

void Input(){
    cin >> num;
    for(int i=0; i<num; i++){
        for(int j=0; j<num; j++){
            cin >> arr[i][j];
        }
    }
}

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Input();
    Stalink(0, 0);
    /*
    첫 번째 0 = 배열의 0부터 시작
    두 번째 0 = count (사람이 몇 명들어왔는지)
    */
    cout << minval;

    return 0;
}