[LeetCode] 79 - Word Search

문제

• 링크: https://leetcode.com/problems/word-search
• 난이도: Medium
• 태그: 배열, 문자열, 백트래킹, 깊이 우선 탐색
• 결과: Time: 0 ms (100%), Space: 14.06 MB (78.96%)

풀이

class Solution {
private:
    int row;
    int col;

public:
    bool exist(vector<vector<char>>& board, string word) {
        row = board.size();
        col = board[0].size();
        for (int r = 0; r < row; ++r)
        {
            for (int c = 0; c < col; ++c)
            {
                if (solve(board, word, r, c, 0))
                {
                    return true;
                }
            }
        }

        return false;
    }

    // dfs 함수
    bool solve(vector<vector<char>>& board, string& word, int r, int c, int idx)
    {
        // 범위를 벗어난 경우
        if (r < 0 || r >= row || c < 0 || c >= col) 
        {
            return false;
        }

        // 글자가 맞지 않는 경우
        if (board[r][c] != word[idx])
        {
            return false;
        }

        // 단어를 찾은 경우
        if (idx == word.size() - 1)
        {
            return true;
        }
        
        char ch = board[r][c];
        board[r][c] = '?'; // 이미 방문한 곳으로 돌아오지 않도록 입력으로 들어오지 않는 문자로 치환

        // 상하좌우 탐색
        int dr[4] = { 1, 0, -1, 0 };
        int dc[4] = { 0, 1, 0, -1 };

        for (int dir = 0; dir < 4; ++dir)
        {
            int nr = r + dr[dir];
            int nc = c + dc[dir];
            if (solve(board, word, nr, nc, idx + 1))
            {
                return true;
            }
        }
        
        board[r][c] = ch; // 원래 문자로 되돌리기
        return false;
    }
};

결국 그리드에서 경로를 찾는 문제이다. 다만, 최단 경로를 찾는게 아니라 특정한 순서를 만족하는 경로를 찾고 있고 방문 여부에 대한 처리가 섞이면 안되기 때문에 BFS가 아닌 DFS를 사용해야한다.

처음에는 방문 배열을 추가로 선언해서 방문 여부를 기록했지만, AI와 풀이를 되짚어보는 과정에서 알파벳이 아닌 문자로 임시 치환하는 방식으로 개선했다.

배운 점과 후기

나도 모르게 “경로”하면 BFS를 떠올리고 있었다. 최단경로 찾기에서는 BFS가 유용하지만, 이 문제에서는 DFS를 고려해야했다. BFS로 구현을 시작하다가 시간을 좀 더 잡아먹게 됐다. 문제를 풀기 전에 전략을 더 잘 세워야겠다. 그러려면 대충 이런 문제에는 이런 알고리즘 같은 식의 매핑이 아니라 각각의 알고리즘에 대해 더 이론적인 공부가 필요하겠다.

이 포스트는 달레 스터디(4주차)에서 진행한 Blind 75 문제집 풀이의 일부입니다.