BOJ - 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)이 주어진다.
출력
꽃을 심기 위한 최소 비용을 출력한다.
구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
using namespace std;
// map
int map[11][11];
bool visited[11][11];
int n;
// joy
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
// ans
int cnt;
int ans = 999999999;
// check
bool check(int y, int x)
{
if(visited[y][x])
return 0;
for(int i=0; i < 4; i++)
{
int ny = y + dy[i];
int nx = x + dx[i];
if(ny < 0 || ny >= n || nx < 0 || nx >= n)
return 0;
if(visited[ny][nx])
return 0;
}
return 1;
}
// seed
int seed(int y, int x)
{
visited[y][x] = 1;
int tmp = map[y][x];
for(int i=0; i < 4; i++)
{
int ny = y + dy[i];
int nx = x + dx[i];
visited[ny][nx] = 1;
tmp += map[ny][nx];
}
return tmp;
}
void delseed(int y, int x)
{
visited[y][x] = 0;
for(int i=0; i < 4; i++)
{
int ny = y + dy[i];
int nx = x + dx[i];
visited[ny][nx] = 0;
}
}
void solution(int cnt, int money)
{
if(cnt == 3)
{
ans = min(money, ans);
return;
}
for(int i=0; i < n; i++)
for(int j=0; j < n; j++)
{
if(check(i, j))
{
solution(cnt+1, money + seed(i, j));
delseed(i, j);
}
}
}
int main()
{
cin >> n;
for(int i=0; i < n; i++)
for(int j=0; j < n; j++)
cin >> map[i][j];
solution(0, 0);
cout << ans << endl;
return 0;
}
SOL
- 꽃을 심을 수 있는지 판단하고
- 심을 수 있다면
- 씨앗을 심고, 최솟 값을 구한 뒤
- 아님말고를 시전한다. (심었던 씨앗을 다시 뽑는다. )
1 2 3 4 5 6 7 8 9 10
for(int i=0; i < n; i++) for(int j=0; j < n; j++) { if(check(i, j)) { solution(cnt+1, money + seed(i, j)); delseed(i, j); } }