[백준] 14620번 : 꽃길 (C++)

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)이 주어진다.

 

 

 

출력 :

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

 

 

 

 

풀이)

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
 
using namespace std;
 
int n;
int dx[] = { 0, -1, 0, 1, 0 };
int dy[] = { 0, 0, 1, 0, -1 };
vector<vector<int>> vec;
vector<vector<int>> visited;
int result = INT_MAX;
int cost = 0;
 
// 해당 좌표로부터 5방향의 꽃 유무를 확인하는 함수
bool check(int a, int b)
{
    for (int i = 0; i < 5; i++)
    {
        int nx = a + dx[i];
        int ny = b + dy[i];
 
        if (nx < 0 || n <= nx) continue;
        if (ny < 0 || n <= ny) continue;
 
        if (visited[nx][ny]) return false;
    }
    return true;
}
 
// 받은 좌표를 기준으로 꽃을 피우는 함수
void setflowers(int a, int b, int &cost)
{
    for (int i = 0; i < 5; i++)
    {
        int nx = a + dx[i];
        int ny = b + dy[i];
 
        if (nx < 0 || n <= nx) continue;
        if (ny < 0 || n <= ny) continue;
 
        visited[nx][ny] = 1;
        cost += vec[nx][ny];
    }
}
 
// 받은 좌표를 기준으로 꽃을 없애는 함수
void eraseflowers(int a, int b, int &cost)
{
    for (int i = 0; i < 5; i++)
    {
        int nx = a + dx[i];
        int ny = b + dy[i];
 
        if (nx < 0 || n <= nx) continue;
        if (ny < 0 || n <= ny) continue;
 
        visited[nx][ny] = 0;
        cost -= vec[nx][ny];
    }
}
 
void recur(int cur, int &cost)
{
    // 3개의 꽃이 피었을 때 
    // 최소 값을 갱신한다.
    if (cur == 3)
    {
        result = min(result, cost);
        return;
    }
 
    // 꽃잎이 모두 폈을 때를 기준으로 하므로,
    // 1부터 n - 1까지만 확인한다.
    for (int i = 1; i < n - 1; i++)
    {
        for (int j = 1; j < n - 1; j++)
        {
            if (check(i, j))
            {
                setflowers(i, j, cost);
                recur(cur + 1, cost);
                eraseflowers(i, j, cost);
            }
        }
    }
}
 
int main()
{
    cin >> n;
    vec.resize(n, vector<int>(n, 0));
    visited.resize(n, vector<int>(n, 0));
 
    // 배열 입력받기
    int temp;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> temp;
            vec[i][j] = temp;
        }
    }
 
    recur(0, cost);
    cout << result;
 
    return 0;
}
 
 

 

 

---

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

14620번: 꽃길