[BOJ] 1987 알파벳

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

1987번: 알파벳

bfs로 풀까 고민하였지만 아무리 봐도 dfs가 구현이 쉬울거 같아서 dfs로 구현하였다.

문제는 시간초과였는데 다행히 그래프의 크기도 작고, 중복되는 알파벳은 접근하지 못한다는 조건도 있어서 많은 경우의 수가 제거되어 제 시간 안에 돌아갔다.

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <climits>

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

vector<string> map_;

int dist[20][20];
bool visit[20][20];
bool check[100];
int dy[]={-1,1,0,0};
int dx[]={0,0,1,-1};

int R,C,ans=0;

void input() {
    cin>>R>>C;
    string s;
    for(int i=0;i<R;i++){
        cin>>s;
        map_.push_back(s);
    }
}

void init() {
}


void solution(int y,int x,int n) {
    char a=map_[y][x];
    if(visit[y][x]||check[a]) return;

    visit[y][x]=true;
    check[a]=true;
    ans=max(n,ans);
    for(int i=0;i<4;i++){
        int ny=dy[i]+y,nx=dx[i]+x;
        if(0<=ny&&ny<R&&0<=nx&&nx<C){
            solution(ny,nx,n+1);
        }
    }
    visit[y][x]=false;
    check[a]=false;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution(0,0,1);
    cout<<ans;
    return 0;
}