[LeetCode] Word Search 🔍 (Java)

🧩 문제 파악

2차원 문자 배열 board와 문자열 word가 주어진다.
board 안에서 인접한 문자들을 연결하여 word를 만들 수 있는지 판단하는 문제이다!

• 🅾️ 같은 칸을 두 번 이상 사용할 수 없음
• ❎ 경로는 오직 상하좌우로만 이동 가능

---

💡 접근 방법

문자 일치 시작점 찾기

• board의 모든 위치를 순회하며 board[i][j] == word.charAt(0)인 위치를 찾는다.
• 해당 위치에서 DFS 탐색을 시작한다.

DFS 탐색

• 현재 위치에서 상하좌우 인접한 위치로 이동하며 word의 다음 문자(index)와 비교한다.
• 방문한 위치는 visited배열로 체크하면서 중복 탐색을 방지한다.
• 탐색 중 경로가 끝까지 도달하면 true를 리턴한다.
• 탐색 실패 시 백트래킹으로 방문 여부를 복원한다.

조건 체크

• board[newR][newC] == word.charAt(index) 이고,
• visited[newR][newC] == false인 경우에만 다음 DFS로 진행한다.
• index == word.lentgth()에 도달하면 탐색 성공이므로 true를 반환한다.

결과 반환

• 모든 경로를 탐색한 후 하나라도 true이면 전체 결과는 true이다.
• 끝까지 찾지 못하면 false를 반환한다.

⚒️ 코드 구현

class Solution {
    // 상하좌우 이동을 위한 방향 배열
    int[][] step = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    // DFS 메서드: 현재 위치에서 다음 문자를 탐색하며 word를 찾는 재귀 함수
    public boolean dfs(char[][] board, String word, boolean[][] visited, int r, int c, int index) {
        // word 전체를 찾았으면 true 리턴
        if (index == word.length()) {
            return true;
        }

        // 4방향으로 탐색 (상하좌우)
        for (int i = 0; i < 4; i++) {
            int newR = r + step[i][0]; 
            int newC = c + step[i][1]; 

            // 범위 안에 있고, 방문하지 않았으며, 다음 문자가 일치하는 경우
            if (newR >= 0 && newR < board.length && newC >= 0 && newC < board[0].length &&
                !visited[newR][newC] && board[newR][newC] == word.charAt(index)) {
                
                visited[newR][newC] = true; // 방문 처리
                // 다음 문자 찾기 위해 재귀 호출
                if (dfs(board, word, visited, newR, newC, index + 1)) {
                    return true; // 경로 찾음
                }
                visited[newR][newC] = false; // 백트래킹
            }
        }

        return false; // 현재 경로로는 word 완성 불가능
    }

    // 시작 지점을 찾고 DFS 수행하는 메서드
    public boolean exist(char[][] board, String word) {
        // board 전체를 순회
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                // word의 첫 글자와 일치하는 지점을 시작점으로 DFS 시작
                if (board[i][j] == word.charAt(0)) {
                    boolean[][] visited = new boolean[board.length][board[i].length]; // 방문 배열 초기화
                    visited[i][j] = true; // 시작 위치 방문 처리

                    // DFS 시작: index는 다음 글자를 의미하므로 1부터 시작
                    if (dfs(board, word, visited, i, j, 1)) {
                        return true; // 찾으면 true 리턴
                    }
                }
            }
        }

        return false; // 모든 경로 탐색해도 찾지 못하면 false
    }
}