[java] Word Search

[참고문제] : https://leetcode.com/problems/word-search/

Word Search - LeetCode

문제 풀이

전형적인 DFS 문제다.

 

생각의 흐름 - Recursive하게 풀어보자.

DFS는 Stack을 사용하거나, Recursive로 풀면 된다.

이 문제는 Stack을 사용하기 보단, 파라미터가 많아 Recursive하게 풀어주면 좀 더 편하게 풀 수 있을 것으로 생각했다.

 

생각의 흐름 - 좌,우,상,하를 체크하자.

좌,우,상,하 방향으로 갈 수 있으니 적절한 예외처리와 최종적으로 True가 반환되는 경우를 잘 체크해서 4가지 방향 중 한 방향으로라도 성공하면 True를 제공하면 된다.

 

생각의 흐름 - Visit 체크를 하자?

방문 여부를 항상 체크해야 한다.

java에서는 Call By Value지만, 객체에 대한 주소위치값을 전달하기 때문에 주의해야 한다.

단순히 visit만 넘기게 되면, 이전에 지나갔던 기록도 고스란히 남아있게 된다. (다시 봐야 하는데 마치 이미 확인한 길인 것처럼) 

따라서, 들어갔다가 나올때는 다시 false를 해주자.

class Solution {
    public boolean exist(char[][] board, String word) {
        int M = board.length;
        int N = board[0].length;
        boolean result = false;

        boolean[][] isVisited = new boolean[M][N];

        for(int i = 0; i < M; i++) {
            for(int j = 0; j < N; j++) {
                if(word.charAt(0) == board[i][j])
                    result = result || dfs(isVisited, board,word.substring(1),i,j,M,N);
                if(result)
                    return true;
            }
        }
        return false;
    }
    
    public boolean dfs(boolean[][] isVisited, char[][] board, String word, int row, int col, int M, int N) {
        if(word.isEmpty())
            return true;
        isVisited[row][col] = true;
        boolean result = false;
        if(col != 0) {
            if(!isVisited[row][col-1] && board[row][col-1] == word.charAt(0))
                result = result || dfs(isVisited,board, word.substring(1), row, col-1, M, N);
        }

        if(col != N-1) {
            if(!isVisited[row][col+1] && board[row][col+1] == word.charAt(0))
                result = result || dfs(isVisited,board, word.substring(1), row, col+1, M, N);
        }

        if(row != 0) {
            if(!isVisited[row-1][col] && board[row-1][col] == word.charAt(0))
                result = result || dfs(isVisited,board, word.substring(1), row-1, col, M, N);
        }

        if(row != M-1) {
            if(!isVisited[row+1][col] && board[row+1][col] == word.charAt(0))
                result = result || dfs(isVisited,board, word.substring(1), row+1, col, M, N);
        }
        
        isVisited[row][col] = false;
        return result;
    }
}