LeetCode: 79번 (Word Search) [JAVA]

문제 링크

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

Word Search - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 주어진 이차원 배열을 돌며 해당 위치의 알파벳이 주어진 word의 시작 알파벳과 동일한 경우 dfs 탐색 시작
2. dfs 탐색 시 위치가 배열 밖인 경우나 중복 방문한 경우 혹은 알파벳이 틀린 경우 탐색을 종료하고, dfs 탐색을 word 길이 만큼하고 마지막 알파벳까지 동일하다면 맞는 경우가 존재하므로 답에 true를 표시하고 종료
3. 그 외에는 일종의 백트래킹 탐색을 위해 방문 표시를 하고 동서남북 dfs 탐색을 하며 이후 다시 방문 표시를 해제
4. 최종 결과를 반환

 문제에서 요구하는 답은 결국 주어진 배열 속 word와 동일한 형태로 타일을 이을 수 있는가에 대한 것이다. 결국 dfs 기반 탐색으로 word의 시작인 부분과 동일한 배열의 위치에서부터 dfs 탐색을 하면된다. 이 때 dfs 탐색에서 기저 조건은 탐색을 word 길이만큼 모두 이행하여 정답이 존재하는 지 답에 true를 표시하고 종료하는 것으로 하고, 이외에 탐색 종료 조건으로 는 예외 사항인 맵 밖인 경우나 중복 방문인 경우로 설정한다. 이후 다음 위치 탐색 시에 일종의 백트래킹 기법을 적용하여, 우선 현 위치에 대해 방문 표시를 true로 하고 동서남북 위치에 대해 dfs 탐색을 호출한 다음, 현 위치에 대한 방문 표시를 다시 false로 수정한다.
 이후 전체 for문을 돌며 탐색이 종료되었다면 결과를 반환한다.

 

class Solution {
    boolean answer = false;
    boolean[][] visited;
    int m, n;

    public boolean exist(char[][] board, String word) {
        m = board.length;
        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) && !answer) {//word의 첫 알파벳과 동일하며 기존 답이 없는 경우
                    visited = new boolean[m][n];
                    check(i, j, 0, board, word);
                }
            }
        }

        return answer;
    }

    void check(int r, int c, int index, char[][] board, String word) {//dfs 탐색
        if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c]) {//맵밖, 중복 방문인 경우
            return;
        }

        if (board[r][c] != word.charAt(index)) {//알파벳이 맞지 않는 경우
            return;
        }

        if (index == word.length() - 1 && board[r][c] == word.charAt(index)) {//끝까지 동일하다면
            answer = true;
            return;
        }

        visited[r][c] = true;//방문 표시

        check(r + 1, c, index + 1, board, word);
        check(r - 1, c, index + 1, board, word);
        check(r, c + 1, index + 1, board, word);
        check(r, c - 1, index + 1, board, word);

        visited[r][c] = false;//방문 표시 해제
    }
}

결과