BOJ 15705 ) 단어 찾기 (C++)

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

15705번: 단어 찾기

 모든 경우를 다 시도해보면 되는 간단한 문제다. 단어의 첫 문자와 배열에 저장된 문자가 같으면 거기서부터 탐색을 시작한다. search 함수에서 시작점으로부터 어느 방향으로 탐색을 진행할지를 정하고, dfs 함수를 호출해 해당 방향으로 계속해서 탐색을 진행한다. 마지막 문자까지 일치하면 true를 반환하고 종료한다. 

#include <iostream>
#include <string>
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
int dx[8]={0,0,1,-1,1,1,-1,-1};
int dy[8]={1,-1,0,0,-1,1,-1,1};

string s;
int N, M;

string arr[100];

bool dfs(int curx, int cury, int cnt, int dir){
    if(cnt == s.size()) return true;
    int nx = curx+dx[dir];
    int ny = cury+dy[dir];
    if(nx<0||ny<0||nx>=N||ny>=M) return false;
    bool chk = false;
    if(arr[nx][ny]==s[cnt]){
        chk = dfs(nx,ny, cnt+1, dir);
    }
    return chk;
}

bool search(int curx, int cury){
    for(int i=0;i<8;i++){
        if(dfs(curx, cury, 1, i)) return true;
    }
    return false;
}

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>s;
    cin>>N>>M;
    for(int i=0;i<N;i++){
        cin>>arr[i];
    }

    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(arr[i][j]==s[0]){
                if(search(i,j)){
                    cout<<1;
                    return 0;
                }
            }
        }
    }
    cout<<0;
    return 0;
}