[백준][C++] 14620 꽃길

www.acmicpc.net/problem/14620

14620번: 꽃길

 

 

 

알고리즘 종류

완전탐색

 

 

 

사고 과정

DFS로 3개의 씨앗을 심을 위치를 선택합니다. 위치를 선택할 때에는 범위 밖으로 나가는지, 다른 꽃과 겹피는지 확인합니다. 이후, 3개를 심을 수 있으면 비용을 계산하여 최소 비용으로 갱신해 줍니다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
 
using namespace std;
 
int n;
int ans=987654321;
 
int cost[11][11];
int mat[11][11];
 
 
bool check(int y, int x){
    if(mat[y][x]) return false;
    if(mat[y+1][x]) return false;
    if(mat[y][x+1]) return false;
    if(mat[y-1][x]) return false;
    if(mat[y][x-1]) return false;
    return true;
}
 
void marking(int y, int x){
    mat[y][x] = 1;
    mat[y+1][x] = 1;
    mat[y][x+1] = 1;
    mat[y-1][x] = 1;
    mat[y][x-1] = 1;
}
 
void unmarking(int y, int x){
    mat[y][x] = 0;
    mat[y+1][x] = 0;
    mat[y][x+1] = 0;
    mat[y-1][x] = 0;
    mat[y][x-1] = 0;
}
 
void dfs(int cnt){
    if(cnt==3){
        int sum = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(mat[i][j]) sum += cost[i][j];
            }
        }
        if(ans > sum) ans = sum;
        return;
    }
    
    for(int i=1; i<n-1; i++){
        for(int j=1; j<n-1; j++){
            if(!check(i, j)) continue;
            marking(i, j);
            dfs(cnt+1);
            unmarking(i, j);
        }
    }
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> cost[i][j];
        }
    }
    
    dfs(0);
    cout << ans << endl;
}
 

 

 

 

시행착오