[알고리즘] 백준 1987

백준 1987번 알파벳

해결 과정 요약

알파벳을 입력 받을 때 A는 0으로 B는 1로 ... 이런식으로 입력받는다.
visited과 alpha배열을 만든다. alpha배열은 알파벳을 몇번 지나왔는지를 담는 배열이다.
완전탐색을 해줄 때 재귀함수 앞뒤에 다음과같이 추가해주면 된다.

visited[ny][nx]++;
alpha[m[ny][nx]]++;
go(ny, nx, cnt+1);
alpha[m[ny][nx]]--;
visited[ny][nx]--;

재귀함수 탈출조건은 다음과 같다.

if(alpha[m[y][x]] == 2){ ret = max(ret, cnt-1); return; }

풀이

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int N,M,ret;
char c;
int m[24][24];
int visited[24][24];
int alpha[30];
int dy[] = {-1,0,1,0};
int dx[] = {0,1,0,-1};

void go(int y, int x, int cnt){
    if(alpha[m[y][x]] == 2){ ret = max(ret, cnt-1); return; }
    for(int i=0; i<4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny < 0 || nx < 0 || ny >= N || nx >= M || visited[ny][nx]) continue;
        visited[ny][nx]++;
        alpha[m[ny][nx]]++;
        go(ny, nx, cnt+1);
        alpha[m[ny][nx]]--;
        visited[ny][nx]--;
    }
    ret = max(ret, cnt);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin >> c;
            m[i][j] = c - 'A';
        }
    }
    visited[0][0] = 1;
    alpha[m[0][0]] = 1;
    go(0, 0, 1);
    cout << ret;
    
    return 0;
}