[BOJ S2][C++] 백준 14620번: 꽃길

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

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

출력

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

 

풀이

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int,int> p;

vector<vector<int>> input;
vector<vector<p>> successPos;

int dx[] = {0,0,-1,1};
int dy[] = {1,-1,0,0};

// 주어진 벡터에 있는 씨앗들이 꽃을 피웠을 때 땅 가격을 구하는 함수
int calcSum(vector<p> v) {
    int sum = 0;
    
    for(int i=0; i<3; i++) {
        p cur = v[i];
        
        sum += input[cur.first][cur.second];  // 씨앗 위치 땅값 더하고
        
        // 위치가 주어진 씨앗의 꽃 피우기
        for(int dir=0; dir<4; dir++) {
            int x = cur.first + dx[dir];
            int y = cur.second + dy[dir];
            
            sum += input[x][y];  // 꽃잎 위치 땅값 더하고
        }
    }
    
    return sum;
}

// 세 좌표에 씨앗을 심었을 때 꽃 개화가 성공하는지 리턴
bool isSucceed(int n, vector<p> &seedpos) {
    vector<vector<bool>> flowerPos (n, vector<bool>(n,false));
    
    // 꽃 위치 벡터에 씨앗 위치 표시
    for(int i=0; i<3; i++)
        flowerPos[seedpos[i].first][seedpos[i].second] = true;
    
    // 꽃 피우기
    for(int i=0; i<3; i++) {
        p cur = seedpos[i];
        
        // (씨앗의 상하좌우에 위치 표시)
        for(int dir=0; dir<4; dir++) {
            int x = cur.first + dx[dir];
            int y = cur.second + dy[dir];
            
            // 꽃이 땅을 벗어나거나 이미 꽃이 있어서 겹친다면
            if(x<0 || x>=n || y<0 || y>=n || flowerPos[x][y])
                return false;
            
            flowerPos[x][y] = true;
        }
    }
    
    return true;
}

int solution (int n) {
    // permutation으로 조합을 구하기 위한 임시 배열
    int tot = n*n;
    vector<bool> tmp(tot, false);
    tmp[tot-1] = tmp[tot-2] = tmp[tot-3] = true;
    
    do{
        vector<p> seedPos;
        // 조합으로 씨앗 위치가 될수 있는 좌표들 구해서 seedPos 벡터에 넣기
        for(int i=0; i<tot; i++) {
            if(tmp[i])
                seedPos.push_back({i/n, i%n});
        }
        
        // 씨앗 심기에 성공하면 successPos에 넣기
        if(isSucceed(n, seedPos))
            successPos.push_back(seedPos);
        
    } while (next_permutation(tmp.begin(), tmp.end()));
    
    // 각 조합의 땅값들의 최솟값 구하기
    int minCost = 3001;
    for(int i=0; i<successPos.size(); i++) {
        int curCost = calcSum(successPos[i]);
        minCost = min(minCost, curCost);
    }
    
    return minCost;
}
int main() {
    int n;
    cin >> n;
    input.assign(n, vector<int>(n,0));
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cin >> input[i][j];
    
    cout << solution(n);
}

/*
 */