[LeetCode] Word Search 풀어보기

https://leetcode.com/problems/word-search/description/

Word Search - LeetCode

이번 문제는 dfs를 활용하는 문제입니다.

bfs를 사용하고 싶어도 귀찮은 문제입니다.

예를 들어 ABAB라는 패턴이 사각형으로 있다면, 

visited상태관리가 어려움을 알 수 있습니다.

 

그리고 m,n이 최대 6이기 때문에 dfs를 활용해야하는 것을 알 수 있습니다.

 

class Solution {
public:
    struct Pos
    {
        int r, c, idx;
    };

    bool exist(vector<vector<char>>& board, string word) {
        N = board.size();
        M = board[0].size();
        len = word.size();

        vector<vector<bool>> visited(N, vector<bool>(M, false));
        for (int i = 0; i < N; ++i)
        {
            for (int j = 0; j < M; ++j)
            {
                if (board[i][j] == word[0])
                {
                    if (len == 1)
                        return true;
                    else
                    {
                        visited[i][j] = true;
                        dfs(i, j, board, word, 0, visited);
                        visited[i][j] = false;
                        if (ans || len == 1)
                            return true;
                    }
                }
            }
        }
        return false;
    }

    void dfs(int r, int c, vector<vector<char>>& board, string& word, int depth,
        vector<vector<bool>>& visited)
    {
        if (ans)
            return;

        for (int i = 0; i < 4; ++i)
        {
            int nr = dr[i] + r;
            int nc = dc[i] + c;
            if (nr >= 0 && nr < N && nc >= 0 && nc < M && !visited[nr][nc] &&
                word[depth + 1] == board[nr][nc])
            {
                if (depth + 1 == len-1)
                {
                    ans = true;
                    return;
                }
                else
                {
                    visited[nr][nc] = true;
                    dfs(nr, nc, board, word, depth + 1, visited);
                    visited[nr][nc] = false;
                }
            }
        }
    }
public:
    int dr[4] = { -1, 0, 1, 0 };
    int dc[4] = { 0, -1, 0, 1 };
    int N, M, len;
    bool ans = false;
};

 

저는 이런식으로 만들었습니다.

재귀를 할 때 밖으로 ans같은걸 빼지 않고 return으로 상태관리하는 것이 저한테는 어렵더라구요 

 

class Solution {
public:
    int dr[4] = {-1, 0, 1, 0};
    int dc[4] = {0, -1, 0, 1};

    int N, M;

    bool exist(vector<vector<char>>& board, string word)
    {
        N = board.size();
        M = board[0].size();

        for (int r = 0; r < N; ++r)
        {
            for (int c = 0; c < M; ++c)
            {
                if (board[r][c] == word[0])
                {
                    if (dfs(r, c, board, word, 0))
                        return true;
                }
            }
        }

        return false;
    }

    bool dfs(int r, int c,
             vector<vector<char>>& board,
             const string& word,
             int depth)
    {
        if (depth == word.size() - 1)
            return true;

        char temp = board[r][c];
        board[r][c] = '#';

        for (int i = 0; i < 4; ++i)
        {
            int nr = r + dr[i];
            int nc = c + dc[i];

            if (nr < 0 || nr >= N || nc < 0 || nc >= M)
                continue;

            if (board[nr][nc] != word[depth + 1])
                continue;

            if (dfs(nr, nc, board, word, depth + 1))
            {
                board[r][c] = temp;
                return true;
            }
        }

        board[r][c] = temp;
        return false;
    }
};

이는 그것을 사용한 방법입니다.