[BOJ] 1987번 알파벳

https://www.acmicpc.net/problem/1987

 

보통 나는 그래프 탐색 문제가 나오면 대부분의 문제를 bfs로 푼다. (dfs보다 bfs가 편하고 좋음)

그래서 이 문제도 처음에 bfs로 접근을 하였는데, 이 문제의 포인트는 똑같은 알파벳을 한 번만 지나야 한다는 점이다.

그러면 queue 안에 지나간 알파벳을 저장할 자료구조가 필요할 것이고 그래서 set을 선택했다. 만약 set안에 알파벳이 있으면 탐색을 안하고 없으면 탐색을 하고 이런식으로... 그랬더니 메모리 초과가 발생했다. 조금만 생각하면 당연한 것이다. 모든 queue에 set을 담아야하면 탐색할 때마다 새로운 set이 추가가 되므로 엄청난 메모리를 먹을 것이다.

 

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair < ll, ll>;
using matrix = vector<vector<ll>>;

const int MAXN = 1e6 + 1;
const int mod = 1e9 + 7;

struct Data {
    int x;
    int y;
    int cnt;
    set<char> s;
};
int n, m;
char a[21][21];
queue<Data> q;
int dx[] = { 1,0,0,-1 };
int dy[] = { 0,1,-1,0 };

void sol() {
    Data d;
    d.x = 0; d.y = 0; d.s.insert(a[0][0]);
    d.cnt = 1;
    q.push(d);
    int result = 0;
    while (!q.empty()) {
        d = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = d.x + dx[i];
            int ny = d.y + dy[i];
            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (!d.s.count(a[nx][ny])) {
                    Data tmp;
                    tmp.x = nx; tmp.y = ny;
                    tmp.s = d.s; tmp.s.insert(a[nx][ny]);
                    tmp.cnt = d.cnt; tmp.cnt++;
                    q.push(tmp);
                    result = max(result, tmp.cnt);
                }
            }
        }
    }
    cout << result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int x, y;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    sol();
    return 0;
}

이게 처음 시도했을 때의 코드이다. 이제 메모리 초과가 떴으니 더 효율적으로 자료구조를 사용하는 방법을 찾아야 했다. 그래서 그냥 bfs방식말고 dfs방식으로 풀면 배열을 딱 한번만 할당해서 풀 수 있을 것 같다는 생각을 하였다.

 

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair < ll, ll>;
using matrix = vector<vector<ll>>;

const int MAXN = 1e6 + 1;
const int mod = 1e9 + 7;

int n, m;
char a[21][21];
int tmp[26];
int dx[] = { 1,0,0,-1 };
int dy[] = { 0,1,-1,0 };
int mx = 0;

void sol(int x,int y,int cnt) {

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (0 <= nx && nx < n && 0 <= ny && ny < m) {
            if (tmp[a[nx][ny]-'A'] == 0) {
                tmp[a[nx][ny] - 'A']++;
                sol(nx, ny, cnt + 1);
                tmp[a[nx][ny] - 'A']--;
            }
            else {
                mx = max(mx, cnt);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int x, y;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    tmp[a[0][0] - 'A']++;
    sol(0,0,1);
    cout << mx;
    return 0;
}

 

dfs 방식에서는 전역변수에 tmp라는 배열을 선언해놓고 사용하였다. 이 문제는 평소 프로그래밍할 때 메모리 초과를 별로 겪어보지 못해서 처음에 왜 메모리 초과가 발생했는지 몰랐는데 앞으로 문제푸는 방식에 대해서 좋은 교훈을 주는 문제였던거 같다.