활용문제 - 알파벳


작성일 : 2018-12-13 00:42:28
조회수 : 71


본문

해당 기법을 이용하여 풀 수 있는 문제 중 대표적인 문제이다. 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;
}

활용문제 - 알파벳 - 알고리즘닷컴
알고리즘 문서에서는 다양한 알고리즘 개념들을 포스팅 하는 곳입니다.