[BOJ] 1987. 알파벳

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

1987번: 알파벳

처음 보드를 입력받을 때, 알파벳을 숫자로 변환해서 저장한다.

문자 - 'A'를 해줘서 A는 0, B는 1, C는 2 이런 식으로 저장된다.

 

방문한 알파벳에는 다시 갈 수 없으므로 방문 체크를 해주어야 한다.

A문자를 방문하면 check [0]에 true 체크, B를 방문하면 check [1]을 true 표시해주는 방식으로

방문 체크를 해나간다.

 

인접한 칸으로 이동할 수 있으면 이동할 좌표와 함께 이동 횟수(cnt) 값을 증가시켜서 함께 보내준다.

 

더 이상 갈 수 없는 경우 탐색을 멈추기 위해 z변수를 두고 다음 칸으로 이동할 수 없을 때마다 값을 증가시켜줬다.

z == 4 가 되면(인접한 상하좌우 네 칸으로 모두 갈 수 없으면) 이동한 횟수를 비교해주고 return 한다.

 

#include <iostream>
#include <string>
using namespace std;
 
int r, c;
int ans;
bool check[26];
int map[20][20];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
void solve(int x, int y, int cnt) {
    
 
    int z = 0;
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];
        if (nx < 0 || ny < 0 || nx >= r || ny >= c) {
            z++;
            continue;
        }
        if (check[map[nx][ny]]) {
            z++;
            continue;
        }
 
        
        check[map[nx][ny]] = true;
        solve(nx, ny, cnt+1);
        check[map[nx][ny]] = false;
    }
 
 
    //인접한 칸으로 더이상 이동할 수 없다.
    if (z == 4) {
        if (ans < cnt) ans = cnt;
        return;
    }
    
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < c; j++) {
            map[i][j] = s[j] - 'A';
        }
    }
 
 
    check[map[0][0]] = true;
    solve(0,0, 1);
 
 
    cout << ans;
    return 0;
}