[LeetCode] 79. Word Search

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

Word Search - LeetCode

Word Search

 

 

일정한 그리드안에 알파벳들이 나열되어있다.

그리고 또 다른 알파벳문자열이 주어졌을때, 그리드 안에서 인접한 알파벳들을 연결해 해당 문자열을 만들 수 있는지 묻는 문제다.

 

컨셉만 보면 되게 간단해보였다.

먼저 이중 for문을 이용해 첫 글자에 해당하는 것들을 찾아준뒤,

그 문자를 기준으로 상,하,좌,우로 한칸씩 이동해 연결된 글자가 나오는지 DFS를 이용해 찾아주면 되기 떄문이다.

그런데 이 과정에서 뭘 잘못했었는지 삽질을 상당히 하고 Time Exceeded가 계속 발생했다.

결국엔 해결했다.

 

DFS 쪽 코드만 잘 짜주면 되는 문제였다.

아래는 전체 풀이 코드다.

 

class Solution {
public:
    vector<vector<char>> board;
    string word;
    bool exist(vector<vector<char>>& board, string word) {
        this->board = board;
        this->word = word;
        int chk[6][6];
        for (int i=0; i<board.size(); i++) for (int j=0; j<board[i].size(); j++) chk[i][j] = 0;
        for (int i=0; i<board.size(); i++) for (int j=0; j<board[i].size(); j++) if (board[i][j]==word[0] && search(make_pair(i,j),0,chk)) return true;
        return false;
    }
    bool search(pair<int,int> cur, int num, int chk[6][6]) {
        if (num == this->word.size()) return true;
        int y = cur.first, x = cur.second;
        if (x<0 || y<0 || x==this->board[0].size() || y==this->board.size() || chk[y][x]==1 || this->board[y][x]!=this->word[num]) return false;
        chk[y][x] = 1;
        bool ret = search(make_pair(y-1,x),num+1, chk) || search(make_pair(y,x-1),num+1,chk) || search(make_pair(y+1,x),num+1,chk) || search(make_pair(y,x+1),num+1,chk);
        chk[y][x] = 0;
        return ret;        
    }
};