(Matrix, Medium) Word Search

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

처음에 BFS로 풀어보려고 시도했는데, visited 체크가 과하다는 생각이 들었다.
왜냐면 각 경로마다 한 번씩이지 글로벌하게 중복체크가 들어가선 안되기 때문이다.
그럼 큐에 넣을 때마다 각각의 visited 체크 배열(또는 무엇이든)이 들어가야 한다.

그에 따라 체크하는 로직도 너무 복잡해지고.. 이건 DFS가 적절한 문제로 보인다.

DFS로 푸는 경우 board자체에 마킹했다가 다시 풀어줄 수 있으므로
경로 당 visited 체크하는데 좋다.

class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == word.charAt(0)) {
                    if (dfs(board, i, j, 0, word)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, int i, int j, int idx, String word) {
        if (idx == word.length()) {
            return true;
        }
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
            return false;
        }
        if (board[i][j] != word.charAt(idx)) {
            return false;
        }

        char temp = board[i][j];
        board[i][j] = '#';

        boolean found =
            dfs(board, i + 1, j, idx + 1, word) || // 아래
            dfs(board, i - 1, j, idx + 1, word) || // 위
            dfs(board, i, j + 1, idx + 1, word) || // 오른쪽
            dfs(board, i, j - 1, idx + 1, word);   // 왼쪽

        board[i][j] = temp;

        return found;
    }
}

여기서 좀 더 나아가면 다음과 같은 프루닝(가지치기)을 추가할 수 있다.

• (알파벳 수 비교) 보드에 등장하는 각 알파벳 수가 실제 단어의 각 알파벳 수보다 적으면 정답에 도달할 수 없다.