BOJ 1987 - 알파벳
“비트마스킹”
BOJ 1987 - 알파벳
문제 링크
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 0x3f3f3f3f;
using namespace std;
int R, C, maxD;
char board[22][22];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int maxdist = 0;
void dfs(int r, int c, int dist, int mask)
{
int idx = board[r][c] - 65;
if (mask & (1 << idx)) {
return ;
}
mask = mask | (1 << idx); // mask |= (1 << idx);
dist += 1;
maxdist = max(dist, maxdist);
for (int dir = 0; dir < 4; dir++) {
int nx = r + dx[dir];
int ny = c + dy[dir];
if (nx < 0 || nx >= R || ny < 0 || ny >= C)
continue;
dfs(nx, ny, dist, mask);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> R >> C;
for (int i = 0; i < R; i++) {
string s; cin >> s;
for (int j = 0; j < s.length(); j++) {
board[i][j] = s[j];
}
}
dfs(0, 0, 0, 0);
cout << maxdist << '\n';
return 0;
}
깊이 우선 탐색(dfs)을 통해, 알파벳을 중복하지 않고 갈 수 있는 경로 중 가장 긴 경로의 길이를 출력하면 된다. 특정한 알파벳의 타일을 밟았을 때, 그 알파벳을 밟았다는 것을 적절히 체크해준 후, 현재 밟고 있는 타일의 알파벳이 밟은 적이 있는 알파벳인 경우 탈락시키면서 길이를 체크하여 가장 길이가 긴 알파벳의 경로를 출력하면 되겠다.
매 경로마다 알파벳을 체크할 때, 예를 들어
bool vis[26]이런 식의 배열을 쓴다고 쳤을 때 한번의 경로 탐색에 대해서 체크한 타일의 경우, dfs를 돌면서 다시 해제해줘야 하는데 (한번의 경로 탐색의 체크 결과가 다른 경로 탐색에 영향을 주게 하지 않아야 한다), 바보같이 그런 생각을 못하고 다른 우회로를 찾아버렸다. 그것이 비트마스킹이다.사실 비트마스킹을 처음부터 떠올린 것은 아니고 처음에는 매 함수 호출마다 배열을 초기화시키기 위해,
bool vis[26]대신vector<int>vis(26, 0)을 사용해 함수 호출 때마다 매번 배열을 복사했다. 함수 호출이 많은데 매번 배열을 복사하기 때문인지 시간초과가 발생했다. 그래서 알아본 결과, 비트마스킹을 사용하면 비슷한 작업을 시간을 절약하면서 진행할 수 있다는 것을 알고 비트마스킹을 사용하게 되었다.비트마스킹에 대해서 공부하고 싶다면 아래 링크 참조.
- 마스크는 함수 호출마다 매번 복사되는 value인데, 정수 하나로 배열의 역할을 할 수 있으니 매우 * INT_MAX 효과적인 체크 방법이라고 볼 수 있겠다!
