# Word Search

**알고리즘 : DFS**\
**DFS = 파고드는 문제!**\
**조건을 만족하면 계속 깊이 파고든다!**

**알고리즘->Java로 구현**

```java
class Solution {//DFS
    int m,n;
    int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    public boolean exist(char[][] board, String word) {
        //error check
        if(board == null ||board.length == 0 || board[0].length == 0) {return false;}
        
        //creat and set value of data structure
        m = board.length;
        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(dfs(board,visited,i,j,0,word)) {return true;}//계속 파고든다! 최종적으로 true이면 true를 리턴!
            }
        }
        return false;
    }
    private boolean dfs(char[][] board, boolean[][] visited, int x, int y, int index, String word) {
        if(index == word.length()) return true;//마지막 철자까지 다 비교하면 true를 리턴하게 된다.
        if(x<0 || x>=m ||y<0 || y>=n) return false;
        if(visited[x][y]) return false;//한번 방문했던 것은 방문하지 않기 위해!
        if(board[x][y] != word.charAt(index)) return false;
        
        //board[x][y] == word.charAt(index) 선택받은 자들은 아래를 수행~!
        visited[x][y] = true;
        for(int[] dir:dirs) {//4방으로 돌린다.
            int newX = x + dir[0];
            int newY = y + dir[1];
            if(dfs(board,visited,newX,newY,index+1,word)){//다음 철자와 비교하는 dfs 재귀 호출!
                return true;
            }
        }
        visited[x][y] = false;//다시 안가기 위해 false를 저장하고, 앞서 호출한 곳에 false리턴한다!
        return false;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://heunnajo.gitbook.io/algorithms-problem-solving-skills/graph-dfs-bfs/word-search.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.