[LeetCode] 79. Word Search (java)

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

 

문제 파악

2차원 배열 board가 주어졌을 때, 동서남북으로 인접한 글자를 이어서 word를 만들 수 있다면 true를, 만들 수 없다면 false를 return하기

 

문제 풀이

📌 완전탐색

• 백트래킹

백트래킹

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

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

        return false;
    }

    int[] dx = {0, 1, 0, -1};
    int[] dy = {1, 0, -1, 0};

    boolean backtracking(int x, int y, int searchIdx, char[][] board, String word, boolean[][] visited) {
        if (searchIdx == word.length()) 
            return true;
        
        int m = board.length; int n = board[0].length;
        for (int d = 0; d < 4; d++) {
            int nextX = x + dx[d];
            int nextY = y + dy[d];

            if (nextX >= n || nextX < 0 || nextY >= m || nextY < 0 || visited[nextY][nextX]) continue;

            if (board[nextY][nextX] == word.charAt(searchIdx)) {
                visited[nextY][nextX] = true;
                if (backtracking(nextX, nextY, searchIdx + 1, board, word, visited)) 
                    return true;
                visited[nextY][nextX] = false;
            }
        }

        return false;
    }
}

 

📊 실행 결과

 

 

NOTE

✅ main함수에서도 방문처리 해주는 거 잊지 말기