[BOJ] 14620. 꽃길

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

14620번: 꽃길

화단에 씨앗 세 개를 심어서 1년 후 세 씨앗 모두 꽃잎이 만개하도록 씨앗의 위치를 정해줘야 하는 문제이다.

그리고 꽃이 피는 화단의 비용이 최소여야한다.

 

테두리 부분(씨앗을 심으면 화단을 넘어가는 부분)을 제외하고 모든 칸에서 씨앗을 심는 경우를 구해준다.

심을 칸과 심을 칸의 상하좌우 부분(꽃이 피는 부분)에 이미 다른 꽃이 있으면 그 칸은 씨앗을 심지 않고 넘어간다.

 

씨앗을 심을 수 있다면, 심은 것을 체크해주고 다음으로 씨앗을 심을 곳을 정해준다.

세 개의 씨앗을 심을 곳을 모두 정해줬다면 꽃이 피는 땅의 비용을 계산해서 최솟값과 비교해준다.

 

#include <iostream>
using namespace std;
 
int n, ans;
int cost[10][10];
bool check[10][10];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
int calc() {
    int sum = 0 ;
    int cnt = 0;
 
    //꽃이 펴있는 칸을 계산
    //꽃 세개가 차지하는 칸은 15개이므로 꽃이 있는 모든 칸의 비용을 더해줬다면 탐색을 중단 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (check[i][j]) {
                sum += cost[i][j];
                cnt++;
                if (cnt == 15) return sum;
            }
        }
    }
}
 
 
 
//씨앗을 심을 땅을 골라준다.
void select(int cnt) {
    if (cnt == 3) {
        // 세 씨앗을 모두 심었으면 비용을 계산
        int tmp = calc();
        if (ans == -1 || ans > tmp)
            ans = tmp;
 
        return;
    }
 
    
 
    //모든 땅에 대해서 꽃을 심어본다.
    //꽃이 화단 밖으로 나가면 죽으므로 피었을때 화단 밖으로 나가는 경우(테두리 부분)는 제외한다.
    for (int i = 1; i < n - 1; i++) {
 
        for (int j = 1; j < n - 1; j++) {
 
            //꽃이 피는 곳에 다른 꽃 없는지 체크
            bool flag = true;
            for (int k = 0; k < 4; k++) {
                int nx = i + dx[k];
                int ny = j + dy[k];
 
                //꽃이 피어야하는 곳에 이미 다른 꽃이 있다면 해당 칸에는 꽃을 심을 수 없다.
                if (check[nx][ny]) {
                    flag = false;
                    break;
                }
            }
 
 
            
            //꽃이 죽을 것이므로 다음 칸에 심는 경우로 넘어간다.
            if (!flag) continue;
 
 
 
            //i,j칸에 씨앗을 심는 경우
            //꽃이 필 수 있는 경우 꽃이 피는 자리를 표시해둔다.
            check[i][j] = true;
            for (int k = 0; k < 4; k++) {
                int nx = i + dx[k];
                int ny = j + dy[k];
                check[nx][ny] = true;
            }
 
 
            //현재 i,j칸에서 꽃을 심는 것으로 고른 후 하나를 더 심는 경우로 넘어간다.
            select(cnt + 1);
 
 
            //i,j칸에 꽃을 심는 경우가 끝났으므로 다시 false 표시해준다.
            check[i][j] = false;
            for (int k = 0; k < 4; k++) {
                int nx = i + dx[k];
                int ny = j + dy[k];
                check[nx][ny] = false;
            }
 
 
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> cost[i][j];
        }
    }
 
    ans = -1;
 
    select(0);
 
    cout << ans;
    return 0;
 
 
}