[c++] 백준 #1987 알파벳 (190823)

< 풀이 >

완전탐색 문제. bfs 식으로 하면서 하면 되겠지? 하고? 코드를 짰는데 메모리 초과가 나왔다. 비트마스크도 써서 메모리 초과가 날 이유가 없는데 질문검색란에 나처럼 bfs식으로 푼 사람의 질문에 대한 답변을 보니 queue가 문제라고 한다. 뭔가 막연히 queue가 커지면 뻑가서 안된다는데 구체적으로 상상이 잘 안가서 직접 써봤다.

(https://www.acmicpc.net/board/view/40634 에서 가져온 반례이다.)

in:

20 20

ABCDEFGHIJKLMNOPQRST

BCDEFGHIJKLMNOPQRSTU

CDEFGHIJKLMNOPQRSTUV

DEFGHIJKLMNOPQRSTUVW

EFGHIJKLMNOPQRSTUVWX

FGHIJKLMNOPQRSTUVWXY

GHIJKLMNOPQRSTUVWXYZ

HIJKLMNOPQRSTUVWXYZA

IJKLMNOPQRSTUVWXYZAB

JKLMNOPQRSTUVWXYZABC

KLMNOPQRSTUVWXYZABCD

LMNOPQRSTUVWXYZABCDE

MNOPQRSTUVWXYZABCDEF

NOPQRSTUVWXYZABCDEFG

OPQRSTUVWXYZABCDEFGH

PQRSTUVWXYZABCDEFGHI

QRSTUVWXYZABCDEFGHIJ

RSTUVWXYZABCDEFGHIJK

STUVWXYZABCDEFGHIJKL

TUVWXYZABCDEFGHIJKLM

 

out:

26

 

위 답변의 예시를 A부터 bfs를 머릿속으로 잘 돌려보자.

맨 처음에 A가 주변을 탐색할 때 큐에는 { B B }가 들어있고,

여기서 B를 빼내면 { B C C }, 다음 B를 빼내면 { C C C C }, C를 꺼내면 { C C C D D }

또 C를 꺼내면 { C C D D D D } 또 꺼내면 { C D D D D D D }

또 꺼내면 { D D D D D D D D } 이 된다.

여기서 이 예시는 이런 식으로 진행되다보면 B는 2번, C는 4번, D는 8번, ..., 이런 식으로 T는 2^19번 큐에 들어간다.

여기서 나는 비트마스크를 쓰면서 state를 저장했기에 q에 한 번 들어갈 때 (x, y, state, n_alphabet)이렇게 4개의 정보(4*4byte = 16 byte)가 들어가고, 이런 식으로 하면 T까지만 해도

개의 원소가 들어가니까 대충 2^20 = 10^6으로 근사해보면 16MB이다. total queue size는 z까지만 가도 정도가 될 거니까 그러면 거의 16*128MB가 돼서 메모리는 무조건 터진다.

 

그래서 bfs로 풀면 안되고, dfs 식으로 풀면 된다. 난이도는 쉬운 문제였으나 큐 쓸 때 뻑가는 이유를 분석해볼 수 있어서 좋았다.

< 소스코드 >

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

int R, C;
char board[25][25];
int move_x[4] = {1, 0, 0, -1};
int move_y[4] = {0, 1, -1, 0};
int ret = 1;

bool visited[30];
void dfs(int x, int y, int cnt){
    ret = max(ret, cnt);
    for(int i=0; i<4;i++){
        int new_x = x + move_x[i];
        int new_y = y + move_y[i];
        if (new_x < 0 || new_x >= R || new_y < 0 || new_y >= C) continue;
        if (visited[board[new_x][new_y] - 'A' + 1]) continue; // 1 ~ 27사이 숫자
        else {
            visited[board[new_x][new_y] - 'A' + 1] = true;
            dfs(new_x, new_y, cnt+1);   
            visited[board[new_x][new_y] - 'A' + 1] = false;
            //cout << state << '\n';
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> R >> C;
    for(int i=0; i<R;i++){
        cin >> board[i];
    }
    
    visited[board[0][0] - 'A' + 1] = true;
    dfs(0,0,1);
    cout << ret;
    return 0;
}