해당 기법을 이용하여 풀 수 있는 문제 중 대표적인 문제이다. 26개의 알파벳이 무작위로 펼쳐진 공간에서, 중복되는 알파벳을 포함하지 않고 상하좌우 중 한 군데를 골라 계속 이동할 때, 이동할 수 있는 최대 거리를 구하는 문제이다.
해당 문제를 bool visited[26] 같은 형태의 저장공간을 쓰면 상태 하나를 저장할 때마다 26바이트씩 사용하게 되고, 20x20 공간을 돌아다니게 될 경우 Memory limit exceeded 현상이 일어나게 된다. 이제 좀 전에 읽었던 bitmask를 생각해보자. bitmask를 이용하면 알파벳 26글자에 대해 int 변수 하나로 상태를 모두 표현할 수 있으므로, 메모리 효율이 훨씬 좋아지게 된다.
int convert(int x) {
return (1 << (x - 'A'));
}
문제를 풀기 위해 위와 같은 함수 하나를 정의 하였다. <<는 비트를 한 자리씩 왼쪽으로 민다고 생각하면 이해하기 쉽다. 1($2^0$) 부터 x-'A' 만큼 밀면, 알파벳에 해당되는 부분의 비트에만 1을 표시할 수 있게 된다. 이를 이용하여 비트마스크를 만든뒤, and 와 or 연산을 이용하여 비트마스킹 여부를 검사하면서 풀면 쉽게 풀 수 있다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include<iostream>
#include<string>
using namespace std;
string s[21];
int w, h, ans;
int convert(int x) {
return (1 << (x - 'A'));
}
void dfs(int x, int y, int cnt, int bit) {
if (x > 0 && !(bit & convert(s[x - 1][y]))) dfs(x - 1, y, cnt + 1, (bit | convert(s[x - 1][y])));
if (y > 0 && !(bit & convert(s[x][y - 1]))) dfs(x, y - 1, cnt + 1, (bit | convert(s[x][y - 1])));
if (x + 1 < w && !(bit & convert(s[x + 1][y]))) dfs(x + 1, y, cnt + 1, (bit | convert(s[x + 1][y])));
if (y + 1 < h && !(bit & convert(s[x][y + 1]))) dfs(x, y + 1, cnt + 1, (bit | convert(s[x][y + 1])));
if (ans < cnt) {
ans = cnt;
}
}
int main()
{
cin >> w >> h;
for (int i = 0; i < w; i++) cin >> s[i];
dfs(0, 0, 1, (1 << (s[0][0] - 'A')));
cout << ans;
}