[백준 c++] 14620 꽃길

문제 설명

https://www.acmicpc.net/problem/14620
2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다.
진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므로 진아는 다음해 식목일 부터 꽃길을 걸을 수 있다.
하지만 진아에게는 꽃의 씨앗이 세개밖에 없었으므로 세 개의 꽃이 하나도 죽지 않고 1년후에 꽃잎이 만개하길 원한다.
꽃밭은 N*N의 격자 모양이고 진아는 씨앗을 (1,1)~(N,N)의 지점 중 한곳에 심을 수 있다. 꽃의 씨앗은 그림 (a)처럼 심어지며 1년 후 꽃이 피면 그림 (b)모양이 된다.
꽃을 심을 때는 주의할 점이있다. 어떤 씨앗이 꽃이 핀 뒤 다른 꽃잎(혹은 꽃술)과 닿게 될 경우 두 꽃 모두 죽어버린다. 또 화단 밖으로 꽃잎이 나가게 된다면 그 꽃은 죽어버리고 만다.
그림(c)는 세 꽃이 정상적으로 핀 모양이고 그림(d)는 두 꽃이 죽어버린 모양이다.
하이테크 앞 화단의 대여 가격은 격자의 한 점마다 다르기 때문에 진아는 서로 다른 세 씨앗을 모두 꽃이 피게하면서 가장 싼 가격에 화단을 대여하고 싶다.
단 화단을 대여할 때는 꽃잎이 핀 모양을 기준으로 대여를 해야하므로 꽃 하나당 5평의 땅을 대여해야만 한다.
돈이 많지 않은 진아를 위하여 진아가 꽃을 심기 위해 필요한 최소비용을 구해주자!

입력
입력의 첫째 줄에 화단의 한 변의 길이 N(6≤N≤10)이 들어온다.
이후 N개의 줄에 N개씩 화단의 지점당 가격(0≤G≤200)이 주어진다.

출력
꽃을 심기 위한 최소 비용을 출력한다.

아이디어

2차원 배열을 전체 탐색하면서 3개의 지점을 겹치지 않게 골라야한다.
처음에는 이중 for문을 여러개 겹쳐서 짰는데 코드도 매우 길어지고 어디선가 예외처리가 안됐는지 틀렸다.

그래서 이중 for문을 돌리는 함수 내에서 재귀 호출을 하는 식으로 구현했더니 전체를 예외없이 탐색할 수 있었다.

flower함수는 2차원 맵을 탐색한다. cnt가 3이되면 최솟값을 저장하도록한다.
check 함수를 통해 5개의 지점이 다 visited가 0이고 맵 안에 있는지 체크하고 통과하면 해당 좌표를 기준으로 5개 지점을 visited 1로 바꾸고, 5개 지점의 가격을 더해준다. 그리고 다시 flower함수를 재귀 호출한다.
그리고 재귀 호출 다음에 visited를 0으로 해제하는 eraseflower함수를 실행한다.

전체 코드

#include <iostream>
#include <algorithm>
using namespace std;
int n, ret = 987654321;
int a[10][10], v[10][10];
int dy[4] = {0, 1, 0, -1};
int dx[4] = {-1, 0, 1, 0};
int setflower(int y, int x)
{
    int cost = a[y][x];
    v[y][x] = 1;
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        v[ny][nx] = 1;
        cost += a[ny][nx];
    }
    return cost;
}
void eraseflower(int y, int x)
{
    v[y][x] = 0;
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        v[ny][nx] = 0;
    }
}
int check(int y, int x)
{
    if (v[y][x])
        return 0;
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny < 0 || nx < 0 || ny >= n || nx >= n || v[ny][nx])
            return 0;
    }
    return 1;
}

void flower(int cnt, int hap)
{
    if (cnt == 3)
    {
        ret = min(ret, hap);
        return;
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (check(i, j))
            {
                flower(cnt + 1, hap + setflower(i, j));
                eraseflower(i, j);
            }
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> a[i][j];
        }
    }
    flower(0, 0);
    cout << ret << "\n";
}