[백준] 14620번 꽃길

14620번 꽃길

문제

---

2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므로 진아는 다음해 식목일 부터 꽃길을 걸을 수 있다.

하지만 진아에게는 꽃의 씨앗이 세개밖에 없었으므로 세 개의 꽃이 하나도 죽지 않고 1년후에 꽃잎이 만개하길 원한다.

꽃밭은 N*N의 격자 모양이고 진아는 씨앗을 (1,1)~(N,N)의 지점 중 한곳에 심을 수 있다. 꽃의 씨앗은 그림 (a)처럼 심어지며 1년 후 꽃이 피면 그림 (b)모양이 된다.

꽃을 심을 때는 주의할 점이있다. 어떤 씨앗이 꽃이 핀 뒤 다른 꽃잎(혹은 꽃술)과 닿게 될 경우 두 꽃 모두 죽어버린다. 또 화단 밖으로 꽃잎이 나가게 된다면 그 꽃은 죽어버리고 만다.

하이테크 앞 화단의 대여 가격은 격자의 한 점마다 다르기 때문에 진아는 서로 다른 세 씨앗을 모두 꽃이 피게하면서 가장 싼 가격에 화단을 대여하고 싶다.

단 화단을 대여할 때는 꽃잎이 핀 모양을 기준으로 대여를 해야하므로 꽃 하나당 5평의 땅을 대여해야만 한다.

돈이 많지 않은 진아를 위하여 진아가 꽃을 심기 위해 필요한 최소비용을 구해주자!

입력

---

입력의 첫째 줄에 화단의 한 변의 길이 N(6≤N≤10)이 들어온다. 

이후 N개의 줄에 N개씩 화단의 지점당 가격(0≤G≤200)이 주어진다.

출력

---

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

---

풀이)

재귀로 가능한 모든 경우를 확인하는 문제이다.

씨앗이 위치할 수 있는 모든 칸에 하나씩 넣어보며, 3개 넣었을 때 비용을 계산했다.

과정

1. (1,1)부터 그 칸에 씨앗을 넣을 수 있는지 확인한다.

    -->현재 위치, 현재 위치의 상하좌우를 확인해 주위에 겹치는 꽃잎이 없는지 확인, 없을 시 삽입 가능

=> 왜 (1,1)부터 보았는지?

화단 밖으로 꽃잎이 나가게 된다면 그 꽃은 바로 죽으니깐

씨앗이 위치할 수 있는 공간은 (1,1) ~ (N-2,N-2) 공간이라고 생각했다. (인덱스를 0부터라고 생각할 때)

씨앗 공간 예시) 

N=6일때 파란 공간은 씨앗이 발아할 수 있는 위치들

2. 씨앗을 넣을 수 있다면 씨앗을 삽입한 뒤, 다른 칸부터 씨앗을 넣을 수 있는지 다시 확인

   

3. 위의 방법을 반복하며 씨앗을 3개 삽입했다면, 총 화단의 비용 확인

   이전에 확인했던 비용보다 작은 비용일 시, 비용의 최소값 갱신

코드)

#include <stdio.h>
#include <algorithm>
#include<vector>
using namespace std;
 
int N;
vector<vector<bool>> visited;
int cost[10][10];
int result = 999999999;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };

// 씨앗이 심어질 수 있는 공간인지 확인하는 함수
bool check(int y, int x) {
    if (visited[y][x]) return true;
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (visited[ny][nx]) return true;
    }
    return false;
}

//씨앗이 심어진 후 사용한 땅임을 표시하는 함수
int used(int y, int x) {
    int tmp = 0; //사용 땅 비용
    visited[y][x] = true;
    tmp += cost[y][x];
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        visited[ny][nx] = true;
        tmp += cost[ny][nx];
    }
    return tmp;
}

void dfs(int y,int x,int val,int depth) {
    if (depth == 3) {
        result = min(result, val);
        return;
    }
    vector <vector<bool>> temp = visited;
    int i = y, j = x, c;
    for (i; i < N-1; i++) {
        for (j; j < N-1; j++) {
            if (check(i, j)) continue;//5평 땅 중 하나라도 이미 사용
            c = used(i, j); // 5평 땅 사용 표시 + 비용 계산
            dfs(i, j+1, val + c, depth + 1);
            visited = temp; //사용 표시 원래대로 되돌려놓음
        }
        j = 1;
    }
}
 
int main() {
    scanf("%d", &N);
    vector <bool> temp(N, false);
    visited.resize(N,temp);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &cost[i][j]);
        }
    }
    dfs(1, 1, 0, 0);
    printf("%d", result);
    return 0;
}