[c++] LeetCode 79번 Word Search

backtracking을 이용해서 푸는 문제이다.
좌우상하 네가지 방향으로 이동할 수 있고, 한번 방문한 cell은 다시 방문하지 않는다.
word의 시작점은 m*n grid의 어느곳이든 될 수 있으므로, 이중 for 문을 이용해서 탐색을 시도해야한다.

find 라는 method를 정의해서 문제를 해결하였다. 현재까지 matching된 word의 index를 curDepth로 전달시켜준다.
그리고 좌우상하 네 방향을 탐색하고 curDepth를 하나 증가시켜 find를 재귀적으로 호출해준다.

이미 방문했던 곳은 다시 방문하면 안되므로, visted 라는 unordered map을 사용해서 관리를 중복 방문이 일어나지 않도록 관리를 하였다. 

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <stack>
#include <queue>
#include <string>

using namespace std;

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

class Solution
{
public:
    bool isValidPos(int i, int j, int n, int m)
    {
        if (i >= 0 && i < n && j >= 0 && j < m)
        {
            return true;
        }
        return false;
    }
    int makeKey(int x, int y, int m)
    {
        return x * m + y;
    }

    bool answer = false;
    void find(vector<vector<char>> &board, string word, unordered_set<int> &visited, int x, int y, int curDepth)
    {
        int n = board.size();
        int m = board[0].size();
        if (curDepth == word.size() - 1)
        {
            answer = true;
            return;
        }

        for (int k = 0; k < 4; k++)
        {
            int nx = x + dx[k];
            int ny = y + dy[k];

            if (isValidPos(nx, ny, n, m) && board[nx][ny] == word[curDepth + 1] && visited.find(makeKey(nx, ny, m)) == visited.end())
            {
                visited.insert(makeKey(nx, ny, m));
                find(board, word, visited, nx, ny, curDepth + 1);
                visited.erase(makeKey(nx, ny, m));
            }
        }
    }
    bool exist(vector<vector<char>> &board, string word)
    {
        int n = board.size();
        int m = board[0].size();
        unordered_set<int> visited;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (board[i][j] == word[0])
                {
                    visited.insert(makeKey(i, j, m));
                    find(board, word, visited, i, j, 0);
                    visited.erase(makeKey(i, j, m));
                }
                if (answer)
                    break;
            }
            if (answer)
                break;
        }

        return answer;
    }
};