[BOJ] 18809. Gaaaaaaaaaarden

 

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

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

depth와 좌표 정보를 넣었다. 

 

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

G

1 or 2

R

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

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

 

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

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

 

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

 

 

#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; }