[DFS] 14620번 꽃 길

14620번 꽃길

 

https://www.acmicpc.net/problem/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)이 주어진다.

 

출력

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

 

예제 입력

6
1 0 2 3 3 4
1 1 1 1 1 1
0 0 1 1 1 1
3 9 9 0 1 99
9 11 3 1 0 3
12 3 0 0 0 1

 

예제 출력

12

 

해결방법

DFS+조합 문제이다.

나머지 부분은 문제 없이 구현했지만 조합을 하는 부분에서 막혔다.

다시 풀어보고 수정해야겠다...

 

+ 문제를 해결했다!!!

다른 DFS+완탐 문제를 풀어보면서 해결법을 찾았다.

DFS함수를 호출할 때, 현재 row값을 매개변수로 전달해야한다. 전달 받으면 그 row 인덱스를 2중 for문의 i에 넣는다. 이렇게 하면, 현재 행에서 부터 다시 씨앗을 심을 곳을 찾게 되니 시간초과가 안나오게 된다.

 

+ 그런데 현재 행의 1번째 열부터 씨앗을 심을지 확인하는데 선택된 위치보다 앞선 곳도 다시 탐색을 할 수 있으니 중복이 발생 할 수 있을 것 같다. 이는 조금더 이해가 필요하다.

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <bitset>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 11
#define INF 987654321
using namespace std;

int n,ans;
int map[MAX][MAX];
bool chk[MAX][MAX];

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

bool chkSeed(int x,int y){
    for(int i=0; i<5; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if(chk[nx][ny]) return false;
    }
    return true;
}

void setSeed(int x,int y){
    for(int i=0; i<5; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        chk[nx][ny] = true;
    }
}

void resetSeed(int x,int y){
    for(int i=0; i<5; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        chk[nx][ny] = false;
    }
}

int calculate(){
    int sum = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(chk[i][j]) sum += map[i][j];
        }
    }
    return sum;
}

void dfs(int ind,int cnt){
    // 정답을 찾은 경우
    if(cnt == 3){
        ans = min(ans,calculate());
        return;
    }
    
    // DFS 탐색
    for(int i=ind; i<n-1; i++){
        for(int j=1; j<n-1; j++){
            if(chkSeed(i,j)){
                setSeed(i,j);
                dfs(i,cnt+1);
                resetSeed(i,j);
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::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 >> map[i][j];
        }
    }
    
    ans = INF;
    dfs(1,0);
    cout << ans << "\n";
}