[BOJ] 꽃길

[BOJ] 꽃길

Problem URL : 꽃길

#include<iostream>

using namespace std;
int n;
int cost[10][10];
bool chk[10][10];
int ans;

bool seedable(int x, int y) {
    // 순차적으로 심으므로 (dfs를 돌게 되므로)
    // 이전 좌표만 체크해주면 된다.
    return !chk[x - 1][y] && !chk[x][y - 1];
}

void seed(int x, int y, bool mode) {
    chk[x][y] = mode;
    chk[x + 1][y] = mode;
    chk[x - 1][y] = mode;
    chk[x][y + 1] = mode;
    chk[x][y - 1] = mode;
}

void calc() {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (chk[i][j]) {
                sum += cost[i][j];
            }
        }
    }
    if (ans > sum) {
        ans = sum;
    }
}

void dfs(int cnt, int x, int y) {
    if (cnt == 3) {
        calc();
        return;
    }

    for (int j = y + 1; j < n - 1; j++) {
        if (seedable(x, j)) {
            seed(x, j, true);
            dfs(cnt + 1, x, j);
            seed(x, j, false);
        }
    }

    for (int i = x + 1; i < n - 1; i++) {
        for (int j = 1; j < n - 1; j++) {
            if (seedable(i, j)) {
                seed(i, j, true);
                dfs(cnt + 1, i, j);
                seed(i, j, false);
            }
        }
    }
}


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

    cin >> n;

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

    ans = 1e9;
    
    // 가장 바깥 부분 ( i = 0 또는 j =0) 에는 심을 수 없다.
    for (int i = 1; i < n - 1; i++) {
        for (int j = 1; j < n - 1; j++) {
            seed(i, j, true);
            dfs(1, i, j);
            seed(i, j, false);
        }
    }

    cout << ans;
    return 0;
}