Identifying the Problem

주어진 2차원 문자열 board에서 각 요소를 가로 또는 세로로 이어 주어진 word를 만들 수 있는지 판단한다.

EX ) Input: word = "ABCCED" → Output: true

Organizing thoughts

아래 유튜브 영상의 해설을 참고하여 작성하였다.

핵심 아이디어는 우선깊이탐색 (DFS) 를 사용해 탐색한 부분은 흔적을 남기고,

재귀로 반복하며, 다음 글자와 일치하는 경우 count를 증가하며 탐색했다.

Sourcecode

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) 
    {
        for(int i=0; i<board.size(); i++) //board 전체를 탐색
        {
            for(int k=0; k<board[i].size(); k++)
            {
                if(board[i][k] == word.at(0) && dfs(board,i,k,0,word)) 
                    return true; //첫 글자와 board 탐색 값이 같고, 
                    			 //dfs결과 값이 true인 경우 true 리턴
            }
        }
        return false; //default 값 false
    }

public: //글자가 같은 경우 흔적을
    bool dfs(vector<vector<char>>& board, int i, int k, int count, string word)
    {
        if(count == word.size()) //탐색한 글자의 수가 word와 일치하면 true 리턴
            return true;
        
        if(i<0 || i>= board.size() || k<0 || k>=board[i].size() || board[i][k] != word.at(count))
            return false; //탐색하는 요소의 범위가 board의 범위를 벗어나거나
            			  //탐색하는 요소의 값과 글자가 다른 경우 false를 리턴한다.
        				  //이미 지나갔던 부분은 ' '로 흔적을 남겼기에 글자가 다른 경우에 포함한다.
        
        char temp = board[i][k]; //현재 탐색하는 값을 temp에 저장하고
        board[i][k] = ' '; //탐색했던 흔적을 남긴다.
        
        bool found = 
            dfs(board, i+1, k, count+1, word) || 
            dfs(board, i-1, k, count+1, word) ||
            dfs(board, i, k+1, count+1, word) ||
            dfs(board, i, k-1, count+1, word);
            //상하좌우로 재귀로 탐색한다.
        
        board[i][k] = temp; //지웠던 탐색값을 원래대로 되돌린다.
        
        return found;
    }
    
};

New things learned

• 우선 깊이 탐색 (DFS