[백준][1987번][DPS] 알파벳

알파벳

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

<문제>

<코드>

#include <iostream>
#include <stdio.h>
#include <cstdlib>
 
using namespace std;
 
 
char board[20][20];
int check[30];
int R,C,result;
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,-1,1};
 
 
// 보드 내에 점이 위치하는 지 체크하는 함수
int inboard(int x, int y)
{
    if(x>=0 && x<R && y>=0 && y<C)
        return 1;
    else
        return 0;
}
 
int dfs(int depth,int i,int j)
{
 
    if(result<depth)
        result = depth;
    for(int k=0;k<4;k++)
    {
        int ny = i + dy[k];
        int nx = j + dx[k];
 
        if(inboard(ny,nx) == 0)
            continue;
        if(check[board[ny][nx] - 65] == 1)
            continue;
        check[board[ny][nx] - 65] = 1;
        dfs(depth+1,ny,nx);
        check[board[ny][nx] - 65] = 0;
 
    }
 
}
 
 
 
int main()
{
    result = 0;
    cin>>R>>C;
    for(int i=0;i<R;i++)
    {
        for(int j=0;j<C;j++)
        {
            cin>>board[i][j];
        }
    }
    check[board[0][0]-65] = 1;
    dfs(1,0,0);
    cout<<result;
 
}
 

<문제 푼 요령>

1. dfs의 가장 일반적인 문제라고 할 수 있다. 보드 안에 점이 있는지 체크해주기 위해서 inboard 함수를 선언해준다.

2. ny, nx을 함수 내에 선언해주어 함수하나에서 for문으로 동시에 4방향의 재귀함수로 뻗어나가게끔 해준다.

3. ny와 nx를 처음에는 전역변수로 선언해서 오류가 났다. 지역변수로 선언해줘야 함에 유의해야 한다.