[코딩테스트 C++] 알파벳

오늘의 문제

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

알파벳

접근 방식

• 전형적인 dfs문제
• 알파벳이 중복될 수 없다는 점을 평소에 사용하던 visit배열과 접목시키면 된다.
• 26개짜리 배열을 만들어놓고 해당 알파벳을 지난 경우 true로 표시한다. 종료 후에는 다시 false로 바꾼다.
• 왜냐하면 다른 로직에서 해당 알파벳이 있을 수 있기에 원래대로 돌려놓는다.
• 입력이 string으로 주어진것도 모른채로 char로 입력을 받고있었다 ㅋㅋ.. 정신차려!

나의 풀이

#include<iostream>
#include <algorithm>
using namespace std;
int r, c;
const int MAX = 20;
char arr[MAX][MAX];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int alpha[26] = {false};

int dfs(int y, int x){
    int maxi = 0;
    for(int i=0;i<4;i++){
        int mx = x + dx[i];
        int my = y + dy[i];
        int al = arr[my][mx]-'A';
        if(mx >= c || mx <0 || my >= r || my<0)
            continue;
        if(alpha[al] == false){
            alpha[al] = true;
            maxi = max(maxi, dfs(my, mx));
            alpha[al] = false;
        }
    }
    return maxi+1;
}

int solution(){
    alpha[arr[0][0] - 'A'] = true;
    return dfs(0, 0);
}

다른 풀이

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>

using std::scanf;
using std::printf;
using std::vector;
using std::unique;
using std::pair;
using std::swap;

using pii = pair<int, int>;

char board[25][25];
vector<pair<int, int> > s;

int main() {
    int h, w; scanf("%d%d", &h, &w);
    for (int ih = 0; ih < h; ++ih) {
        scanf("%22s", board[ih]);
    }
    s.push_back({0, 1 << board[0][0] - 'A'});
    int gen = 0;
    for ( ; !s.empty(); ++gen) {
        vector<pair<int, int> > olds;
        swap(s, olds);
        olds.erase(unique(olds.begin(), olds.end()), olds.end());

        for (auto& pr : olds) {
            const int p = pr.first;
            const int v = pr.second;
            const int ds[4] = {1, -1, w, -w};
            for (int d : ds) {
                int np = p + d;
                if (np < 0 || np >= h * w || (d % w != 0 && p / w != np / w)) { continue; }
                int nv = v | 1 << board[np / w][np % w] - 'A';
                if (nv == v) continue;
                s.push_back({np, nv});
            }
        }
    }
    printf("%d\n", gen);
}

배울 점

• 중복제거하는 함수가 있었구나 신기 하나 더 배운다.