[leetCode] 79. Word Search

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

Word Search - LeetCode

이 문제는 2차원 배열 내에서의 탐색 문제이다.

여기서 하나의 문자열이 주어지는데, 이 문자열을 해당 배열에 인접한(상하좌우) 공간으로 이동하여 글자를 조합했을 때, 주어진 문자열을 만들어낼 수 있는지 물어보는 문제이다.

 

여기서 하나 생각할 수 있는게 이 문제는 백트래킹 문제임을 생각할 수 있다.

특정 시작점에서 출발해 단어의 글자를 하나씩 매칭하며 나아가다가, 도중에 막히거나 잘못된 길(단어와 일치하지 않는 글자)을 만나면 이전 단계로 되돌아와서(Backtrack) 다른 방향을 탐색해야 하기 때문이다.

 

또한 정해져 있는 문자열을 계속해서 파고들어 찾아야 하기 때문에, DFS방식으로도 생각하여 접근할 수 있다. 

 

아래 코드를 보자.

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int rows = board.size();
        int columns = board[0].size();

        vector<vector<bool>> visitCheck(rows, vector<bool>(columns, false));

        for(int row = 0; row< rows; row++){
            for(int col= 0; col<columns; col++)
            {
                if(board[row][col] == word[0] && search(visitCheck, word, board, row, col, 0))
                {
                    return true;
                }
            }
        }
        return false;

    }

    bool search(vector<vector<bool>>& visitCheck, string word, vector<vector<char>>& board, int row, int col, int index)
    {
        if(word.size() == index) 
            return true;

        if(row < 0 || row >= board.size() || col < 0 || col >= board[0].size())
            return false;
        if(board[row][col] != word[index] || visitCheck[row][col] == true)
            return false;

        visitCheck[row][col] = true;

        bool checkWord = search(visitCheck, word, board, row+1, col, index+1) ||
                        search(visitCheck, word, board, row-1, col, index+1) ||
                        search(visitCheck, word, board, row, col+1, index+1) ||
                        search(visitCheck, word, board, row, col-1, index+1);

        visitCheck[row][col] = false;

        return checkWord;
    }
};

위의 코드처럼, 백트래킹으로 체킹할 수 있는 변수를 하나 두고, for문을 돌아 이중 배열에서 처음 시작 지점을 서칭하여 탐색을 쭉 실행한다.

여기서 상하좌우를 판단하고, 이중배열의 인덱스를 넘어가는지도 체킹한다.

만약 우리가 구하려는 문자열의 길이가 현재 문자열의 길이와 비슷하면 true를 리턴한다. ( 그 이전에 해당 문자가 유사한 문자인지 방문한 곳인지 다 확인해 본다 )