[Backtracking][Medium] 79. Word Search

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

Word Search - LeetCode

 

Q. 주어진 board와 word에서 해당 board 안에 word가 있는지 여부를 반환하라. 

 

 

Solution

 board의 확장 가능한 case에 맞게 모든 상황에 대한 전개가 필요하다. 따라서 backtrack을 사용한다. 

 특정 위치에서는 한번에 하나의 선택만 가능한데, 위, 아래, 좌, 우 방향의 진행이 그것이다. 

 이때 한번 지나왔던 board 위치는 다시 갈 수 없음에 유의한다. 

 

 그렇다면 어디에서 시작해야 하는가?

 전 보드 구간에서 word의 첫 글자가 맞는 위치들에서 시작하면 될 것이다. 

 따라서 진입 지점도 loop를 돌면서 찾아야 한다. 

 

 위 로직을 코드로 옮겨 본다. 

bool exist_DP(vector<vector<char>>& board, string word, int x, int y, vector<bool>& vVisit, int cntHit)
{
    // 조건에 맞게 모든 문자가 word와 같아지면 종료된다.
    if (cntHit >= word.size())
        return true;

    int height = board.size();
    int width = board[0].size();
    int idx = y * width + x;

    int wordIdx = cntHit;

    // left 
    if (x > 0 && !vVisit[idx - 1] && board[y][x - 1] == word[wordIdx])
    {
        vVisit[idx - 1] = true;
        if (exist_DP(board, word, x - 1, y, vVisit, cntHit+1))
            return true;
        vVisit[idx - 1] = false;
    }
    
    // right
    if (x < width-1 && !vVisit[idx + 1] && board[y][x + 1] == word[wordIdx])
    {
        vVisit[idx + 1] = true;
        if (exist_DP(board, word, x + 1, y, vVisit, cntHit + 1))
            return true;
        vVisit[idx + 1] = false;
    }

    // up 
    if (y > 0 && !vVisit[idx - width] && board[y-1][x] == word[wordIdx])
    {
        vVisit[idx - width] = true;
        if (exist_DP(board, word, x, y-1, vVisit, cntHit + 1))
            return true;
        vVisit[idx - width] = false;
    }

    // down
    if (y < height-1 && !vVisit[idx + width] && board[y + 1][x] == word[wordIdx])
    {
        vVisit[idx + width] = true;
        if (exist_DP(board, word, x, y + 1, vVisit, cntHit + 1))
            return true;
        vVisit[idx + width] = false;
    }

    // 어느 지점으로도 진출 불가하면 이 블럭에서는 실패이다.
    return false;
}

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

    vector<bool> vVisit;
    vVisit.resize(width*height, false);

    // 진입 지점을 찾는다.
    for (int y = 0; y < height; ++y)
    {
        for (int x = 0; x < width; ++x)
        {
            if (board[y][x] != word[0])
                continue;

            vVisit[y * width + x] = true;
            if (exist_DP(board, word, x, y, vVisit, 1))
                return true;
            vVisit[y * width + x] = false;
        }
    }
    return false;
}

 

 

적당한 결과를 얻었다. 

 

Note ) 매치류의 퍼즐 게임을 보면 '감염'이라는 개념이 나온다. 

 이런 류의 로직을 만들 때 유용해 보인다.