반응형
https://www.acmicpc.net/problem/18809
18809번: Gaaaaaaaaaarden
첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두고 주어진다. 그 다음 N개의 줄에는 각 줄마다 정원의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0, 1, 2이다. 0은 호수, 1은 배양액을 뿌릴 수 없는 땅, 2는 배양
www.acmicpc.net
BFS와 백트래킹을 이용해 푼 문제였습니다.
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 | #include <iostream> #include <queue> #include <algorithm> #include <cstring> using namespace std; int garden[51][51]; int dx[4] = { 0,0,-1,1 }; int dy[4] = { 1,-1, 0, 0 }; int n, m, g, r, ans; int bfs(); void comb(int g, int r, int x, int y){ if (g == 0 && r == 0) { ans = max(ans, bfs()); return; } for (int i = x; i <= n; i++) { for (int j = 1; j <= m; j++) { if (garden[i][j] == 2 &&(i > x || j > y) ) { if (g > 0) { garden[i][j] = 3; comb(g - 1, r, i, j); } if (r > 0) { garden[i][j] = 4; comb(g, r - 1, i, j); } garden[i][j] = 2; } } } } int bfs() { int tmp[51][51]; queue <pair<int, int>> gq, rq, q; int rd[51][51]; int gd[51][51]; int flower[51][51]; int fcnt = 0; memset(rd, 0, sizeof(rd)); memset(gd, 0, sizeof(gd)); memset(flower, false, sizeof(flower)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (garden[i][j] == 3) { gq.push({ i,j }); gd[i][j] = 1; } if (garden[i][j] == 4) { rq.push({ i,j }); rd[i][j] = 1; } tmp[i][j] = garden[i][j]; } } while (!gq.empty() || !rq.empty()) { int gqsize = gq.size(); int rqsize = rq.size(); while (gqsize--) { int x = gq.front().first; int y = gq.front().second; gq.pop(); if (flower[x][y]) continue; for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (1 <= nx && nx <= n && 1 <= ny && ny <= m) { if ((tmp[nx][ny] == 1 || tmp[nx][ny] == 2) && !flower[nx][ny] && !gd[nx][ny] && !rd[nx][ny]){ gd[nx][ny] = gd[x][y] + 1; gq.push({ nx,ny }); } } } } while (rqsize--) { int x = rq.front().first; int y = rq.front().second; rq.pop(); if (flower[x][y]) continue; for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (1 <= nx && nx <= n && 1 <= ny && ny <= m) { if ((tmp[nx][ny] == 1 || tmp[nx][ny] == 2) && !flower[nx][ny] && !rd[nx][ny]) { //거리가 같으면 if (gd[nx][ny] == rd[x][y] + 1) { flower[nx][ny] = true; fcnt++; } else { rd[nx][ny] = rd[x][y] + 1; rq.push({ nx,ny }); } } } } } } return fcnt; } int main() { cin >> n >> m >> g >> r; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> garden[i][j]; comb(g, r, 1, 0); cout << ans << '\n'; } | cs |
'Algorithm > BFS' 카테고리의 다른 글
| (C++) - 백준(BOJ) 1260번 : DFS와 BFS 답 (0) | 2020.07.13 |
|---|---|
| (C++) - 백준(BOJ) 16985번 : Maaaaaaaaaze (0) | 2020.04.09 |
| (C++) - 백준(BOJ) 2573번 : 빙산 (0) | 2017.03.14 |
| (C++) - 백준(BOJ) 1389 : 케빈 베이컨의 6단계 법칙 (0) | 2017.03.10 |
| (C++) - 백준(BOJ)코딩 2468번 : 안전 영역 답 (0) | 2017.02.20 |