dfs 무방향도 섹션

제목:

방법:

리프 노드에 열거하여 계산하는 코드: (1766MS)

#include <set>
#include <stack>
#include <queue>
#include <vector>
#include <cstdio>
#include <map>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define LL long long int
using namespace std;
const int M=29,INF=0x3fffffff;
int diagram[M][M],n,str[M],ans=-INF;

int cal(void){
    int sum=0;
    for(int i=1;i <= n;i++){
        if(str[i])
            for(int j=1;j <= n;j++){
                if(!str[j]){
                    sum+=diagram[i][j];
                }
            }
    }
    return sum;
}

void dfs(int x){
     if(x > n){
        int x=cal();
        if(x > ans) ans=x;
        return;
     }
     for(int i=0;i < 2;i++){
        str[x]=i;
        dfs(x+1);
        str[x]=!i;
     }
     return;
}

int main(void){
    while(~scanf("%d",&n)){
        ans=-INF;
        for(int i=1;i <= n;i++){
            for(int j=1;j <= n;j++){
                scanf("%d",&diagram[i][j]);
            }
        }
        dfs(1);
        printf("%d
",ans);
    }
    return 0;
}

한 번 변경할 때마다 거리를 변경하는 코드: (297MS)

#include <set>
#include <stack>
#include <queue>
#include <vector>
#include <cstdio>
#include <map>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define LL long long int
using namespace std;
const int M=29,INF=0x3fffffff;
int diagram[M][M],n,str[M],ans=-INF;



void dfs(int x, int sum){
     if(x > n){
        if(sum > ans) ans = sum;
        return;
     }
     for(int i=0;i < 2;i++){
        int temp = 0, key = str[x];
        if(str[x] != i) {
            str[x] = i;
            for(int j = 1; j <= n; j++) {
                if(j != x && str[j] == i) temp -= diagram[j][x];
                else if(str[j] != i) temp += diagram[j][x];
            }
        }
        dfs(x + 1, sum + temp);
        str[x] = key;
     }
     return;
}

int main(void){
    while(~scanf("%d",&n)){
        ans=-INF;
        for(int i=1;i <= n;i++){
            for(int j=1;j <= n;j++){
                scanf("%d",&diagram[i][j]);
            }
        }
        dfs(1, 0);
        printf("%d
",ans);
    }
    return 0;
}