18809번: Gaaaaaaaaaarden
첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두
www.acmicpc.net
알고리즘 종류
- 구현
- 브루트포스
- BFS
사고 과정
0. 땅을 나타내는 구조체를 생성한다.
0-1. 땅의 상태(0,1,2), 배양액의 색, 뿌려진 시간, 꽃이 피었는지 유무
1. 배양액을 뿌릴 땅을 조합으로 구한다.
1-1. 초록색 배양액을 먼저 DFS로 백트랙킹해서 구한다.
1-2. 이후, 붉은색 배양액을 DFS로 백트랙킹해서 구한다.
2. BFS로 배양액을 퍼트린다.
2-1. 1번에서 어떤 땅에 무슨 배양액을 놓을지 구했다. 그 땅으로 BFS를 수행한다.
2-2. 4방향을 탐색한다. 이때, 다음 갈 곳에 다른 색의 배양액이 있으면서, 동시간대이고, 꽃이 피지 않았다면, 꽃을 피운다.
2-3. 4방향으로 탐색하려 배양액이 뿌려질 수 있으면 배양액을 뿌린다.
- 아래 작성한 코드를 보면 더 쉬울 것 같습니다.
구현(C++)
|
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
|
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
struct Soil{
int state = 0; // 땅의 상태, 0:호수, 1:배양액 못 뿌리는 땅 , 2:배양액 뿌릴수 있는 땅
char color = ' ';
int time = 0; // 배양액이 뿌려진 시간
bool flower = false; // 꽃이 되었는지
};
int n, m, g, r;
int answer = 0;
Soil mat[51][51]; // 복사본
Soil mat2[51][51]; // 원본
int isVisited[51][51]; // 배양액이 지나간 곳 표시
int isSelected[11]; // 어디에 무슨 배양액 뿌릴지 선택
vector<pair<int, int> > v; // 배양액 뿌릴 수 있는 땅들
int dir[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
bool isValid(int y, int x){
return (y>=0 && y<n) && (x>=0 && x<m);
}
void go(){
memset(isVisited, 0, sizeof(isVisited));
memcpy(mat, mat2, sizeof(mat2));
// 선택한 땅에 배양액 놓기
for(int i=0; i<v.size(); i++){
int y = v[i].first;
int x = v[i].second;
if(isSelected[i] == 1) mat[y][x].color = 'g';
else if(isSelected[i] == 2) mat[y][x].color = 'r';
}
// BFS를 수행하기 위해서 queue에 배양액이 놓인 땅 저장하기
queue<pair<int, int> > q;
for(int i=0; i<v.size(); i++){
if(isSelected[i] == 0) continue;
q.push({v[i].first, v[i].second});
isVisited[v[i].first][v[i].second] = 1;
}
int time = 1;
int cnt = 0;
while(!q.empty()){
int size = q.size();
for(int i=0; i<size; i++){
int y = q.front().first;
int x = q.front().second;
char color = mat[y][x].color;
q.pop();
if(mat[y][x].flower) continue; // queue에 이미 넣은 땅인데 꽃이 되었으면 수행하지 않는다.
for(int d=0; d<4; d++){
int ny = y + dir[d][0];
int nx = x + dir[d][1];
// 배양액이 퍼질 다음 땅에 동시간대에 뿌려진 다른 배양액이 있다면 꽃이 된다.
if((mat[ny][nx].color=='r' && color=='g') || (mat[ny][nx].color=='g' && color=='r') ){
if(time == mat[ny][nx].time && !mat[ny][nx].flower){ // 동시간 && 꽃이 피지 않은 땅
mat[ny][nx].flower = true;
cnt ++;
}
}
// 배양액이 못가는 조건들
if(isVisited[ny][nx]) continue; // 배양액이 이미 지나간 땅
if(!isValid(ny, nx)) continue; // 범위 밖
if(mat[ny][nx].state==0) continue; // 호수
if(mat[ny][nx].flower) continue; // 꽃이 된 땅
isVisited[ny][nx] = 1;
// 아무것도 없는 땅이면 배양액이 퍼진다.
mat[ny][nx].color = color;
mat[ny][nx].time = time;
q.push({ny, nx});
}
}
time++;
}
answer = max(answer, cnt);
}
void choice_red(int idx, int cnt){
if(cnt == r){
// 두 배양액을 뿌릴 곳을 모두 찾았으면 BFS 시작
go();
}
for(int i=idx; i<v.size(); i++){
if(isSelected[i]) continue;
isSelected[i] = 2;
choice_red(i+1, cnt+1);
isSelected[i] = 0;
}
}
void choice_green(int idx, int cnt){
if(cnt == g){
// 붉은 색 배양액 뿌릴 곳 찾기
choice_red(0, 0);
}
for(int i=idx; i<v.size(); i++){
if(isSelected[i]) continue;
isSelected[i] = 1;
choice_green(i+1, cnt+1);
isSelected[i] = 0;
}
}
int main(void){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n >> m >> g >> r;
int num;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cin >> num;
mat2[i][j].state = num;
if(num == 2){
v.push_back({i,j});
}
}
}
// 초록색 배양액 뿌릴 곳 찾기
choice_green(0, 0);
cout << answer << endl;
}
|
cs |
시행착오
1. 땅의 정보가 저장된 원본 mat2을 가지고 BFS를 수행하는 실수를 했다. mat으로 복사해서 사용했다.
2. 땅의 숫자가 2인 위치를 저장한 배열 v의 모든 요소를 queue에 넣는 실수를 했다. 모든 숫자가 2인 땅에 배양액에 뿌러질 것이 아니라서 배양액이 뿌리질 땅의 y와 x를 queue에 저장했다.
3. 아래 코드는 꽃이 만들어지는 조건을 나타낸 코드이다. 여기서 실수한 부분은 !mat[ny][nx].flower 조건을 추가하지 않은 것이다. 이 조건을 추가하지 않으면 같은 땅에 꽃이 여러 개 카운팅 된다. 왜냐하면 배양액이 퍼진 1방향을 제외하고 3방향에서 다른 색의 배양액이 온다면, 한 곳에 3개의 꽃이 생겼다고 카운팅되게 된다. 따라서, 꽃이 없는 곳인지 확인하는 조건을 넣어야 한다. 본인은 이것을 확인하고 위해서 꽃이 생성되는 y, x 좌표를 모두 출력해 보았고, 동일한 좌표가 여러 개 찍은 것을 확인하고 그제서야 수정할 수 있었다.
|
1
2
3
4
5
6
|
if((mat[ny][nx].color=='r' && color=='g') || (mat[ny][nx].color=='g' && color=='r') ){
if(time == mat[ny][nx].time && !mat[ny][nx].flower){ // 동시간 && 꽃이 피지 않은 땅
mat[ny][nx].flower = true;
cnt ++;
}
}
|
cs |
4. 시간은 1시간 20분 정도 소요된 것 같다. 1시간 이내에 풀기 위해서 노력해야겠다. 다소 시간을 소모했던 곳은 배양액 2곳을 뿌릴 알고리즘을 생각하는 것과 위 2번을 찾는 데에서 많이 소모했다.
'코딩 공부 > 백준' 카테고리의 다른 글
| [백준][C++] 17836 공주님을 구해라! (0) | 2021.03.23 |
|---|---|
| [백준][C++] 2024 선분 덮기 (0) | 2021.03.23 |
| [백준][C++] 10217 KCM Travel (0) | 2021.03.19 |
| [백준][C++] 9370 미확인 도착지 (0) | 2021.03.18 |
| [백준][C++] 1167 트리의 지름 (0) | 2021.03.17 |