BOJ/14620

<꽃길>

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>


int arr[12][12];
int mem[12][12];

int check(int j, int k) {
    if (mem[j][k] == 0 && mem[j + 1][k] == 0 && mem[j - 1][k] == 0 && mem[j][k + 1] == 0 && mem[j][k - 1] == 0) {
        return 0;
    }
    else {
        return -1;
    }
}

void paint(int j, int k) {
    mem[j][k] = 1;
    mem[j + 1][k] = 1;
    mem[j - 1][k] = 1;
    mem[j][k + 1] = 1;
    mem[j][k - 1] = 1;
}

void remove(int j, int k) {
    mem[j][k] = 0;
    mem[j + 1][k] = 0;
    mem[j - 1][k] = 0;
    mem[j][k + 1] = 0;
    mem[j][k - 1] = 0;
}

int main() {

    int num;
    scanf("%d", &num);

    
    for (int i = 0; i < 12; i++) {
        memset(mem[i], 0, sizeof(int) * 12);
    }
    for (int i = 0; i < num; i++) {
        for (int k = 0; k < num; k++) {
            scanf("%d", &arr[i][k]);
        }
    }
    
    int x1, x2, x3, y1, y2, y3;

    
    int sum = 900000000;
    for ( y1 = 1; y1 < num - 1; y1++) {
        for (x1 = 1; x1 < num - 1; x1++) {//1
            for (y2 = 1; y2 < num - 1; y2++) {
                for (x2 = 1; x2 < num - 1; x2++) {//2
                    for (y3 = 1; y3 < num - 1; y3++) {
                        for (x3 = 1; x3 < num - 1; x3++) {//2
                            int f1 = 0, f2 = 0, f3 = 0;
                            if (check(y1, x1) == 0) {
                                paint(y1, x1);
                                f1 = 1;
                            }
                            if (check(y2, x2) == 0) {
                                paint(y2, x2);
                                f2 = 1;
                            }
                            if (check(y3, x3) == 0) {
                                paint(y3, x3);
                                f3 = 1;
                            }
                            if (f1 == 1 && f2 == 1 && f3 == 1) {
                                int s1 = arr[y1][x1] + arr[y1][x1 + 1] + arr[y1][x1 - 1] + arr[y1 + 1][x1] + arr[y1 - 1][x1];
                                int s2 = arr[y2][x2] + arr[y2][x2 + 1] + arr[y2][x2 - 1] + arr[y2 + 1][x2] + arr[y2 - 1][x2];
                                int s3 = arr[y3][x3] + arr[y3][x3 + 1] + arr[y3][x3 - 1] + arr[y3 + 1][x3] + arr[y3 - 1][x3];
                                int ss = s1 + s2 + s3;
                                if (ss < sum) {
                                    sum = ss;
                                }
                            }
                            remove(y1, x1); remove(y2, x2); remove(y3, x3);
                        }
                    }
                }
            }
        }
    }

    printf("%d\n", sum);
}

카테고리가 부르트포스고 돌아야 할 2차원 배열의 N도 작아서 그냥 완전탐색 돌아버렸다.

최대 8^6번 돌기 때문에 그냥 저냥 될거라 생각했는데 진짜 됐다.

다른 풀이들 보니 시간복잡도 줄이기 위해 dfs사용하던데 아직 재귀에 익숙하지 않아서 사용하지 못하였음ㅠ

땅값 2차원 배열과 같은 크기의 2차원 배열 mem을 선언하여 0으로 초기화 한 후 심을 수 있는지 없는지 체크하였다.