[BOJ] 18809. Gaaaaaaaaaarden

 

* 배양액들의 조합을 구해서 배치한다. 

* 큐를 [초록색 배양액, 빨간색 배양액] 으로 두 개를 사용하는데 

depth와 좌표 정보를 넣었다. 

 

depth는 처음에 문제를 잘 못 이해해서 예시를 보고 추가했다. 

G

1 or 2

R

이렇게 되어있을 때만 가운데 좌표에 꽃이 필 수 있다. 

동시에 도달했을 때의 정보를 넣어줘야 하는데 그 정보를 depth로 기록했다. 

 

*depth를 기록했다면 이 정보를 빠르게 찾아내야 하는데, 이 정보는 dp[][] 배열에 기록해서 

빨간색 배양액이 다음에 갈 곳에 이미 초록색 배양액이 있다. -> dp[nx][ny] 가 depth + 1 이면 초록색 배양액이 방금 전에 도달한 곳이다라는 정보를 찾아낼 수 있다. -> 꽃을 틔운다. 

 

*50*50 인데 조합까지 해서 그런지 시간이 꽤 걸린다. 최적화는 나중에..

 

 

?

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 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170

#include <iostream> #include <vector> #include <algorithm> #include <queue> #include <cstring>   using namespace std; int n, m, g, r, ans = -1; int map[51][51]; //0은 호수, 1은 배양액을 뿌릴 수 있는 땅, 2 뿌릴 수 없는 땅 //3은 초록색 배양액 4는 빨간색 배양액 5는 꽃으로 정의한다. vector<int> seq;   //배양액은 모두 뿌려야 한다. typedef pair<int, int> pp; typedef pair<int, pp> ipp; vector<pp> enable; bool chk[11], visited[51][51];   int dx[4] = {-1,1,0,0}, dy[4] = {0,0,-1,1};   void print() {     cout << '\n';     for (int i = 0; i < n; i++) {         for(int j = 0; j < m; j++) {             if (map[i][j] == 0) cout << "x ";             else                            cout << map[i][j] << ' ';         }         cout << '\n';     }     cout << '\n'; } int bfs() {     queue<ipp> green, red;       int dp[51][51] = {{0}};     memset(visited, 0, sizeof(visited));       for (auto i : enable) {         if (map[i.first][i.second] ==3) {             green.push(ipp(0,i));                       }         if (map[i.first][i.second]==4) red.push(ipp(0,i));     }       int ret = 0;           while(!green.empty() && !red.empty()) {         //두 배양액이 만나면 꽃을 틔운다.         int size = green.size();         bool flag = false;         //더 이상 나아갈 곳이 없으면 반복문 중단         //그린 먼저         while(size--) {             int x = green.front().second.first;             int y = green.front().second.second;             int depth = green.front().first;               green.pop();               if (map[x][y] == 5) continue;             for (int i = 0; i < 4; i++) {                 int nx = x + dx[i];                 int ny = y + dy[i];                   if (nx < 0 || nx>= n || ny < 0 || ny>= m || !map[nx][ny] || map[nx][ny] == 5) continue;                 if (map[nx][ny] == map[x][y]) continue;                   if (map[nx][ny] == 1 || map[nx][ny] == 2) {                     //해당 배양액으로 바꾼다.                     map[nx][ny] = map[x][y];                     green.push(ipp(depth+1, pp(nx, ny)));                     dp[nx][ny] = depth+1;                 }             }         }           size =red.size();           while(size--) {             int x = red.front().second.first;             int y = red.front().second.second;             int depth = red.front().first;               red.pop();                           if (map[x][y] == 5) continue;               for (int i = 0; i < 4; i++) {                 int nx = x + dx[i];                 int ny = y + dy[i];                   if (nx < 0 || nx>= n || ny < 0 || ny>= m || !map[nx][ny] || map[nx][ny] == 5) continue;                 if (map[nx][ny] == map[x][y]) continue;                   if (map[nx][ny] == 7 - map[x][y]) {                     if (dp[nx][ny] == depth+1) {                         map[nx][ny] = 5;                         ret++;                     }                 }                   if (map[nx][ny] == 1 || map[nx][ny] == 2) {                     //해당 배양액으로 바꾼다.                     map[nx][ny] = map[x][y];                     red.push(ipp(depth+1,pp(nx, ny)));                                       }             }         }     }     return ret; } void dfs(int idx, int cntg, int cntr) {     if (cntg == 0 && cntr == 0) {         int c_map[51][51];         memcpy(c_map, map, sizeof(map));           int res = bfs();                  ans = ans > res ? ans : res;           memcpy(map, c_map, sizeof(map));         return;     }       for (int i = idx; i < enable.size(); i++) {         if (!chk[i]) {             chk[i] = true;             if (cntg-1 >=0){                 map[enable[i].first][enable[i].second] = 3;                 dfs(i+1,cntg-1, cntr);             }             if (cntr -1 >= 0) {                 map[enable[i].first][enable[i].second] = 4;                 dfs(i+1,cntg, cntr-1);             }             map[enable[i].first][enable[i].second] = 2;             chk[i] = false;         }     } } int main() {       ios_base::sync_with_stdio(0);     cin.tie(0);       cin >> n >> m >> g >> r;     for (int i = 0; i < n; i++) {         for(int j = 0; j < m; j++ ) {             cin >> map[i][j];             if (map[i][j] == 2) {                 enable.push_back(pp(i, j));             }         }     }//input     vector<int> requid;       for (int i = 0; i < g; i++) requid.push_back(3);     for (int i = 0; i < r; i++) requid.push_back(4);       dfs(0, g, r);     //뿌릴 수 있는 땅에 배양액을 배치한다.     cout << ans << '\n';       return 0; }