https://www.acmicpc.net/problem/14620
14620번: 꽃길
2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므로 진아는 다음해 식목일 부터 꽃길을 걸을 수 있다. 하지만 진아에게는 꽃의 씨앗이 세개밖에 없었으므로 세 개의 꽃이 하나도 죽지 않고 1년후에 꽃잎이 만개하길 원한다. 꽃밭은 N*N의 격자 모양이고 진아는 씨앗을 (1,1)~(N,N)의 지점 중 한곳에 심을 수
www.acmicpc.net
화단에 씨앗 세 개를 심어서 1년 후 세 씨앗 모두 꽃잎이 만개하도록 씨앗의 위치를 정해줘야 하는 문제이다.
그리고 꽃이 피는 화단의 비용이 최소여야한다.
테두리 부분(씨앗을 심으면 화단을 넘어가는 부분)을 제외하고 모든 칸에서 씨앗을 심는 경우를 구해준다.
심을 칸과 심을 칸의 상하좌우 부분(꽃이 피는 부분)에 이미 다른 꽃이 있으면 그 칸은 씨앗을 심지 않고 넘어간다.
씨앗을 심을 수 있다면, 심은 것을 체크해주고 다음으로 씨앗을 심을 곳을 정해준다.
세 개의 씨앗을 심을 곳을 모두 정해줬다면 꽃이 피는 땅의 비용을 계산해서 최솟값과 비교해준다.
|
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
#include <iostream>
using namespace std;
int n, ans;
int cost[10][10];
bool check[10][10];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int calc() {
int sum = 0 ;
int cnt = 0;
//꽃이 펴있는 칸을 계산
//꽃 세개가 차지하는 칸은 15개이므로 꽃이 있는 모든 칸의 비용을 더해줬다면 탐색을 중단
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (check[i][j]) {
sum += cost[i][j];
cnt++;
if (cnt == 15) return sum;
}
}
}
}
//씨앗을 심을 땅을 골라준다.
void select(int cnt) {
if (cnt == 3) {
// 세 씨앗을 모두 심었으면 비용을 계산
int tmp = calc();
if (ans == -1 || ans > tmp)
ans = tmp;
return;
}
//모든 땅에 대해서 꽃을 심어본다.
//꽃이 화단 밖으로 나가면 죽으므로 피었을때 화단 밖으로 나가는 경우(테두리 부분)는 제외한다.
for (int i = 1; i < n - 1; i++) {
for (int j = 1; j < n - 1; j++) {
//꽃이 피는 곳에 다른 꽃 없는지 체크
bool flag = true;
for (int k = 0; k < 4; k++) {
int nx = i + dx[k];
int ny = j + dy[k];
//꽃이 피어야하는 곳에 이미 다른 꽃이 있다면 해당 칸에는 꽃을 심을 수 없다.
if (check[nx][ny]) {
flag = false;
break;
}
}
//꽃이 죽을 것이므로 다음 칸에 심는 경우로 넘어간다.
if (!flag) continue;
//i,j칸에 씨앗을 심는 경우
//꽃이 필 수 있는 경우 꽃이 피는 자리를 표시해둔다.
check[i][j] = true;
for (int k = 0; k < 4; k++) {
int nx = i + dx[k];
int ny = j + dy[k];
check[nx][ny] = true;
}
//현재 i,j칸에서 꽃을 심는 것으로 고른 후 하나를 더 심는 경우로 넘어간다.
select(cnt + 1);
//i,j칸에 꽃을 심는 경우가 끝났으므로 다시 false 표시해준다.
check[i][j] = false;
for (int k = 0; k < 4; k++) {
int nx = i + dx[k];
int ny = j + dy[k];
check[nx][ny] = false;
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> cost[i][j];
}
}
ans = -1;
select(0);
cout << ans;
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 2636. 치즈 (0) | 2019.07.08 |
|---|---|
| [BOJ] 1347. 미로 만들기 (0) | 2019.07.06 |
| [BOJ] 14889. 스타트와 링크 (0) | 2019.07.06 |
| [BOJ] 3184. 양 (0) | 2019.07.06 |
| [BOJ] 1026. 보물 (0) | 2019.07.06 |