Word Search

🔗 문제 링크

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

🔍 문제 설명

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

⚠️ 제한사항

• m = board.length

• n = board[i].length

• $1 <= m, n <= 6$

• $1 <= word.length <= 15$

• board and word consists of only lowercase and uppercase English letters.

---

🗝 풀이 (언어 : Java)

이 문제는 각 순서의 단어가 맞는 경우에 단어 끝까지 한큐에 확인하는게 좋으니까 BFS가 아니라 DFS를 사용하는 것이 맞다. 이 문제를 풀면서 어려웠던 점은 같은 시작점 케이스에서 되는 경우와 안되는 경우가 같이 있는데, 해당 위치의 글자가 방문했던 것인지 체크하는 2차원 배열 visited를 공유하면서 겹쳐서 실패한 경우가 끝나면 배열을 다시 false로 초기화를 시켜야 하는데 어디서 시켜주어야 할지 몰랐다. 재귀호출한 곳 아래에서 해주면 된다. 방법은 알았으나 감을 잡으려면 비슷한 문제를 다시 만나서 풀어봐야 할 것 같다.

class Solution {
    private boolean[][] visited;

    private boolean dfs(char[][] board, String word, int x, int y, int idx) {
        // 인덱스가 범위를 넘거나, 해당 순서의 글자가 안맞거나, 이미 사용한 글자인 경우 탈락
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] != word.charAt(idx) || visited[x][y])
            return false;
        // 위에서 통과했고 마지막 순서 글자면 정답 존재
        if (idx == word.length() - 1)
            return true;
        // 중복사용 안하도록 체크
        visited[x][y] = true;
        // 상하좌우 체크해서 한쪽이라도 만족하면 true로 계속 진행
        if (dfs(board, word, x - 1, y, idx + 1) || dfs(board, word, x + 1, y, idx + 1)
            || dfs(board, word, x, y - 1, idx + 1) || dfs(board, word, x, y + 1, idx + 1))
            return true;
        // 상하좌우에 맞는 케이스가 없는 경우 방문 배열 원복하고 false
        visited[x][y] = false;
        return false;
    }

    public boolean exist(char[][] board, String word) {
        int vertical = board.length;
        int horizontal = board[0].length;
        visited = new boolean[vertical][horizontal];
        // DFS로 모든 지점에서 스타트
        for (int i = 0; i < vertical; i++) {
            for (int j = 0; j < horizontal; j++) {
                // 원래 순서, 역순의 단어와 첫글자가 일치할 경우 DFS실시, 방문 여부 배열은 매번 초기화
                if (dfs(board, word, i, j, 0))
                    return true;
            }
        }
        return false;
    }
}