발상
주어진 맵을 행 단위로 분리했을 때 어떤 위치 에 학생이 올 수 있는지 여부에 영향을 미 칠 수 있는 위치는 한정되어 있다.
그림으로 나타내면 아래와 같다.
2행의 빨간색 위치에 학생이 배치되어 있다면 3행의 초록색 위치에는 학생을 배치할 수 없는 식이다.
이렇게 행의 배치를 결정했다면 행에 배치할 수 있는 위치도 함께 결정된다.
어떤 행의 학생 배치를 완료할 때마다 배치 상태를 비트마스크로 저장하고 배치 별 최적값을 저장해 정답을 구할 수 있다.
이전 문제들에서 많이 나온 개념인데, 행의 배치가 결정된 순간 행에 배치할 수 있는 최대 학생 수는 항상 확정일 수 밖에 없다.
물론 탐색이 끝나기 전까지 실제로 알 수는 없지만 개념적으로 그렇다는 뜻이다.
따라서 우리가 코드로 해야하는 일은 각 행마다, 그리고 각 행의 학생 배치마다 이후에 배치될 수 있는 최대 학생 수를 구하는 일이다.
그 후 (행에 배치한 학생 수) + (행에 배치될 수 있는 최대 학생 수) 중 가장 큰 조합을 골라 반환하는 식으로 재귀 호출 코드를 작성해 문제를 해결할 수 있다.
풀이 개념은 간단하지만 비트 마스크 문제들이 으레 그렇듯, 코드가 조금 복잡하다.
점화식
코드
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
using namespace std;
using ll = long long;
int n, m;
vector<vector<int>> arr, dp, ch;
int r(int row, int st) {
if (row > n) return 0;
int& ret = dp[row][st];
if (ret != -1) return ret;
ret = 0;
vector<int> fp;
for (int i = 0; i < m; i++) {
if (((1 << i) & st) == 0 && arr[row][i + 1] == 0) {
fp.push_back(i); // 배치 가능한 위치 탐색 및 저장
// 1. 이전 행에서 대각선 위치에 학생이 배치된 적 없으며
// 2. 현재 행에서 책상이 부숴지지 않은 위치여야 함.
}
}
for (int i = 0; i < (1 << fp.size()); i++) { // 배치 가능한 위치 조합
vector<int> cp(m + 1); // 학생 배치
bool si = false;
int nxp = 0; // 현재 열의 학생 배치 비트 마스크
int ads = 0; // 현재 행에 배치하게 되는 학생 수
for (int j = 0; j < fp.size(); j++) {
if (((1 << j) & i) > 0) {
if (fp[j] > 0 && cp[fp[j] - 1] == 1) {
// 연속으로 2명 이상의 학생을 배치하는 조합은 생략
si = true;
break;
}
cp[fp[j]] = 1; // 학생 수 위치 기록
ads++; // 학생 수 기록
if (fp[j] > 0) {
// 왼쪽 대각선 비트마스크 기록
nxp |= (1 << (fp[j] - 1));
}
if (fp[j] < m - 1) {
// 오른쪽 대각선 비트마스크 기록
nxp |= (1 << (fp[j] + 1));
}
}
}
if (si == true) continue;
// (i+1)~n행까지의 학생 수 + 현재 행 학생 수 조합 중 최댓값 반환
int s1 = r(row + 1, nxp) + ads; ret = ret > s1 ? ret : s1;
}
return ret;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int tc; cin >> tc;
while (tc--) {
cin >> n >> m; arr = ch = vector<vector<int>>(n + 1, vector<int>(m + 1)); dp = vector<vector<int>>(n + 1, vector<int>(1 << m, -1));
for (int i = 1; i <= n; i++) {
string s; cin >> s;
for (int j = 1; j <= m; j++) {
if (s[j - 1] == '.') {
arr[i][j] = 0;
}
else {
arr[i][j] = 1;
}
}
}
cout << r(1, 0) << "\n";
}
return 0;
}