[LeetCode] 79. Word Search - 깊이우선탐색(DFS) + 문자열(String) JAVA

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

코드설명

깊이우선탐색(DFS) + 문자열(String) 을 활용합니다.

 

모든 n x m 을 돌면서, 첫 시작단어가 같다면 단어를 DFS로 탐색해나갑니다.

이떄, 특이사항은 word.substring(1)으로 맨 첫번쨰 단어는 하나씩 제외하면서 이후의 단어들을 맞추어나갑니다.

코드

class Solution {
    public boolean exist(char[][] board, String word) {
        boolean ret = false;
        for(int i=0; i<board.length; i++){
            for(int j=0;j<board[i].length; j++){
               if(board[i][j] == word.charAt(0)){
                    boolean[][] visited = new boolean[board.length][board[i].length];
                    visited[i][j] = true;
                    ret |= dfs(board, word.substring(1), i, j, visited);    
               } 
            }
        }
        return ret;
    }

    boolean dfs(char[][] board, String word, int r, int c, boolean[][] visited){
        if(word.length() == 0){
            return true;
        }

        boolean ret = false;
        for(int[] dir : new int[][] { {-1, 0}, {1, 0}, {0, -1}, {0, 1}}){
            int nr = r + dir[0];
            int nc = c + dir[1];
            if(nr < 0 || nr >= board.length || nc < 0 || nc >= board[0].length){
                continue;
            }
            if( visited[nr][nc] == false && (board[nr][nc] == word.charAt(0))){
                visited[nr][nc] = true;
                ret |= dfs(board, word.substring(1), nr, nc, visited);
                visited[nr][nc] = false;
            } 
        }
        return ret;
    }

}