[BOJ][C++] 1987 알파벳

[BOJ][C++] 1987 알파벳

 

문제

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

 

풀이

(0,0)에서 시작하여 알파벳 중복이 되지 않도록 이동을 합니다. 

이 때, 이미 이동한 칸은 지나갈 수 없고 말이 최대 몇 칸을 이동하는지 구하는 문제입니다. 

모든 경우를 매번 따져보는 것은 효율적이지 않기 때문에 현재 위치에서 이동시키고 돌아오도록 코드를 짰습니다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
using namespace std;
int R, C, res = 0;
char map[20][20];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
vector<char> alphabet;
int now = 0;
bool checking(char now) {
    for (int i = 0; i < alphabet.size(); i++) {
        if (now == alphabet.at(i)) {
            return false;
        }
    }
    return true;
}
void Move(int x, int y, int cnt) {
    if (cnt > res) {
        res = cnt;
    }
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
        if (checking(map[nx][ny])) {
            alphabet.push_back(map[nx][ny]);
            cnt++;
            
            Move(nx, ny, cnt);

            cnt--;
            alphabet.erase(alphabet.end()-1);
        }
        else {
            if (cnt > res) {
                res = cnt;
                return;
            }
        }
    }


}
int main() {
    scanf("%d %d", &R, &C);

    for (int i = 0; i < R; i++) {
        scanf("%s", map[i]);
    }

    alphabet.push_back(map[0][0]);
    Move(0,0,1);
    printf("%d\n", res);
}