백준 14620 꽃길

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

#include <iostream>
#include <vector>

#define INF 987654321

using namespace std;

int ny[4] = {-1, 1, 0, 0};
int nx[4] = {0, 0, -1, 1};

int ans = INF;
int n;

bool visit[10][10];
int flw[10][10];

void dfs(int sum, int cnt){

    if (cnt == 3) {
        ans=min(ans, sum);
        return;

    }

    for (int i = 1; i < n - 1; i++) {
        for (int j = 1; j < n - 1; j++) {

            int check = 0;
            int newX, newY;
            for (int k = 0; k < 4; k++) {
                newY = i + ny[k];
                newX = j + nx[k];
                if (visit[newY][newX])continue;
                check++;
            }
            if (check == 4) {
                int curSum=flw[i][j];
                for (int k = 0; k < 4; k++) {
                    visit[i + ny[k]][j + nx[k]] = true;
                    curSum += flw[i + ny[k]][j + nx[k]];
                }
                visit[i][j] = true;
                dfs(sum + curSum, cnt + 1);
                for (int k = 0; k < 4; k++) {
                    visit[i + ny[k]][j + nx[k]] = false;
                }
                visit[i][j] = false;

            }
        }
    }

}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    cin >> n;



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

    dfs(0, 0);


    cout << ans;



    return 0;
}

 1. 문제

화단이 있고 본인은 이 화단을 구매하여 심을 씨앗을 세 개 들고 있다. 이 꽃은 피면 화단의 상하좌우로 꽃잎이 피어나는데, 꽃이 겹칠 경우 두 꽃 모두 시들게 된다. 이때, 꽃이 시들지 않는 선에서 피우기 위해 필요한 화단의 가격의 최솟값을 구하는 문제이다. 

2. 풀이

브루트포스 문제이다. 이 문제에서는 최대 10*10의 화단이 주어지는데, 화단의 가장 바깥쪽에 꽃을 심으면 피어났을 때 화단을 넘어갈 수 있으므로 연산은 8*8에서 진행된다. 이 중 3개를 고르는 모든 경우의 수를 구하는 문제이므로 대략 64C3=41664 정도의 연산이 필요하다. 즉, 제한 시간인 2초 안에는 모든 연산이 가능하다. 백트래킹 같은 느낌의 문제로 모든 경우를 확인하기로 했다.

  for (int i = 1; i < n - 1; i++) {
        for (int j = 1; j < n - 1; j++) {

            int check = 0;
            int newX, newY;
            for (int k = 0; k < 4; k++) {
                newY = i + ny[k];
                newX = j + nx[k];
                if (visit[newY][newX])continue;
                check++;
            }
            ...

 위에서 언급했듯이 화단의 바깥쪽은 확인하지 않는다. 우선 dfs 함수에서 해당 꽃이 피었을 때 다른 꽃의 범위를 침범하지 않는지 확인한다. 

if (check == 4) {
                int curSum=flw[i][j];
                for (int k = 0; k < 4; k++) {
                    visit[i + ny[k]][j + nx[k]] = true;
                    curSum += flw[i + ny[k]][j + nx[k]];
                }
                visit[i][j] = true;
                dfs(sum + curSum, cnt + 1);
                for (int k = 0; k < 4; k++) {
                    visit[i + ny[k]][j + nx[k]] = false;
                }
                visit[i][j] = false;

            }

 상하좌우의 모든 꽃잎을 확인했다면 현재 꽃이 피었을 때 화단의 가격의 합을 구한다. visit 배열에는 꽃봉오리와 꽃잎의 위치를 적고, 꽃의 개수와 화단의 가격을 재귀로 넘긴다. 연산이 끝나면 해당 꽃은 다시 회수한다.

 

    if (cnt == 3) {
        ans=min(ans, sum);
        return;

    }

 꽃의 개수가 3개가 되었다면 화단의 최소 가격 ans를 갱신한다. 연산이 끝난 후 ans를 출력하면 답을 구할 수 있다.