[알고리즘] 백준 14620

백준 14620번 꽃길

해결 과정 요약

canPlant, plantOrPull 함수를 잘 만든다.
plantOrPull은 파라미터인 toggle값에 따라서 심을지 뽑을지 결정된다.
이어서 dfs함수를 작성해주는데 탈출조건을 잘 써주고
심는 경우와 심지 않는 경우 두가지를 모두 확인해준다.

// dfs 함수 내부
// 심는 경우
int result = plantOrPull(y, x, 1);
dfs(y, x+2, account + result);
plantOrPull(y, x, 0);
// 심지 않는 경우
dfs(y, x+1, account);

풀이

#include <bits/stdc++.h>
using namespace std;

int seed;
int min_account = 3000;
int price[10][10];
int flower[10][10];
int n;
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};

bool canPlant(int y, int x){
    if(flower[y][x]) return false;
    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 || flower[ny][nx])
            return false;
    }
    return true;
}

int plantOrPull(int y, int x, int toggle){
    int sum = 0;
    flower[y][x] = toggle;
    sum += price[y][x];
    for(int i=0; i<4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        flower[ny][nx] = toggle;
        sum += price[ny][nx];
    }
    if(toggle) seed++;
    else seed--;
    return sum;
}

void dfs(int y, int x, int account){
    if(account >= min_account) return;
    if(seed == 3){
        min_account = min(account, min_account);
        return;
    }
    if(x == n){
        dfs(y+1, 0, account);
        return;
    }
    if(y == n) return;
    if(!canPlant(y, x)){
        dfs(y, x+1, account);
        return;
    }
    int result = plantOrPull(y, x, 1);
    dfs(y, x+2, account + result);
    plantOrPull(y, x, 0);
    
    dfs(y, x+1, account);
    return;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> price[i][j];
        }
    }
    dfs(0,0,0);
    cout << min_account;
    
    return 0;
}

코멘트

전에 풀었던 색종이 붙이기와 유사한 문제