[BOJ] 16988. Baaaaaaaaaduk2 (Easy)

*조합을 이용하여 2개의 빈칸 좌표에 내 돌(1)을 놓은 후, 죽일 수 있는 상대 돌의 최대값을 계산한다. 

*죽일 수 있는 상대 돌 그룹은 내 돌(1)로 둘러싸여져 있어야 한다. 

하지만 그것을 증명하는 것보다는 돌 그룹의 상하좌우에 빈칸(0)이 있으면 그 돌 그룹은 죽을 수 없다고 간주하는 것이 더 구현하기 쉽다. 

 

#include <iostream> #include <vector> #include <queue> #include <cstring> using namespace std; int n, m, ans = 0; int map[21][21]; typedef pair<int, int> pp; vector<pp> emt, enemy; int emtCnt = 0; bool visited[500], chk[21][21]; int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 }; void check() { //죽일 수 있는 상대방의 돌의 개수를 찾는다. //= 죽일 수 있다. (1로 완전히 둘러싸여있다. => 0이 근처에 하나도 없다.) memset(chk, 0, sizeof(chk)); int res = 0; int cnt = enemy.size(); for (int i = 0; i < cnt; i++) { if (chk[enemy[i].first][enemy[i].second]) continue; queue<pp> q; q.push(pp(enemy[i].first, enemy[i].second)); //적의 돌부터 하나하나 살펴본다. int tmp = 1; bool flag = true; chk[enemy[i].first][enemy[i].second] = true; while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); for (int j = 0; j < 4; j++) { int nx = x + dx[j]; int ny = y + dy[j]; if (nx < 0 || nx >= n || ny < 0 || ny >= m || chk[nx][ny]) continue; if (!map[nx][ny]) { //이 돌은 죽을 수 없음 flag = false; } if (map[nx][ny] == 2) { tmp++; chk[nx][ny] = true; q.push(pp(nx, ny)); } } } if (!flag) tmp = 0; //cout << enemy[i].first << " " << enemy[i].second << " " << tmp << " " << flag << '\n'; res += tmp; } ans = ans > res ? ans : res; } void dfs(int idx, int cnt) { if (cnt == 2) { check(); return; } for (int i = idx; i < emtCnt; i++) { if (!visited[i]) { visited[i] = true; map[emt[i].first][emt[i].second] = 1; dfs(i + 1, cnt + 1); visited[i] = false; map[emt[i].first][emt[i].second] = 0; } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> map[i][j]; if (map[i][j] == 0) { //빈칸에 돌을 둘 수 있다. emt.push_back(pp(i, j)); } else if (map[i][j] == 2) { enemy.push_back(pp(i, j)); } } } emtCnt = emt.size(); //일단 돌을 2개 놓는다. dfs(0, 0); cout << ans << '\n'; return 0; }