[DFS, 난이도 중상] 백준 1987번 알파벳

DFS 첫 문제부터 조금 욕심을 내서 정답율 30%인 문제를 골랐다. 

한 번만에 성공해서 되게 좋았다.

DFS는 주로 스택이나 재귀 함수를 이용하는데, 개인적으로 재귀 함수가 훨씬 편한 것 같다.

 

제일 먼저 node라는 이름을 가진 구조체를 선언하였다.

BFS 문제들을 풀면서, 탐색 문제에는 구조체를 활용하는것이 효과적이라는 사실을 깨달아서 바로 활용해 본 것이다.

구조체 안의 변수는 깊이,좌표 정보들로 구성시켰다.

 

시작점은 1행 1열이므로 좌표는 (0,0), 깊이는 1인 구조체 node를 맨 처음dfs 매개변수에 넣으며 시작했다.

상하좌우를 탐색하며 현재까지 처음 마주보는 알파벳만 그 좌표를 방문처리 하고 재귀함수를 호출했다.

그리고 재귀함수에서 나왔을 때 방문처리는 취소했다.

 

dfs문 중간에서 -65값을 이용한 것은 아스키코드 값으로 맞춰주기 위한 것이다.

대문자 A는 65이므로 대문자 알파벳의 첫 인덱스값 0을 만들기 위해서는 65를 빼야하는 것이다.

B는 66-65=1

C는 67-65=2

D는 68-65=3 ...

이렇게 방문처리를 하면 중복된 알파벳을 만날 수 없다.

DFS함수가 종료 될 때마다 node가 얼마나 많은 칸을 지나왔나 즉, 깊이의 최대 값을 업데이트 해주면 된다.

 

 

 

 

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <string>
using namespace std;
struct node{
    int depth,x,y;
};
bool alphabet[26];
char map[21][21];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
int r,c;
int ans=0;
int maxi(int a,int b){
    if(a>b)return a;
    else return b;
}
void dfs(node f){
    for(int i=0;i<4;i++){
        if(f.x+dx[i]<0 || f.y+dy[i]<0 || f.x+dx[i]>=r || f.y+dy[i]>=c) continue;
        if(!alphabet[(int)map[f.x+dx[i]][f.y+dy[i]]-65]){
            alphabet[(int)map[f.x+dx[i]][f.y+dy[i]]-65] = true;
            dfs(node{f.depth+1,f.x+dx[i],f.y+dy[i]});
            alphabet[(int)map[f.x+dx[i]][f.y+dy[i]]-65] = false;
        }
    }
    ans=maxi(ans,f.depth);
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    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];
        }
    }
    alphabet[(int)map[0][0]-65]=true;
    dfs(node{1,0,0});
    cout << ans;
}