[Algorithm] WordSearch

Problem

Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell,
where "adjacent" cells are those horizontally or vertically neighboring. The
same letter cell may not be used more than once.

Example

board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]

Test Case

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

---

간단하게 정리하자면 2차원 배열로 여러 알파벳들이 나열되서 주어지고
찾아야 하는 단어가 주어진다.

그러면 찾아야 하는 단어가 주어진 2차원 배열에 들어있는지 찾으면 된다.
여기서 핵심은 그냥 단어를 하나씩 뽑는게 아니라 순서대로 선을 그어서 뽑을 수 있어야 한다!!

Code

public class WordSearch{

	public static void main(String[] args){
    	char[][] grid = { {'A','B','C','E'},
			  {'S','F','C','S'},
	                  {'A','D','E','E'}}
                      
	String word = "ABCCEDZ";                      
    WordSearch a = new WordSearch();
    System.out.println(a.solve(grid, word));   
                         
    }
    
    int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    int m,n;
    private boolean solve(char[][] grid, String word){
    	//1
        if(grid==null || grid.length==0 || grid[0].length ==0)
        	return false;
	m = grid.length;
    n = grid[0].length;
    boolean[][] visited = new boolean[m][n];
    for(int i=0; i<m; i++){
    	for(int j=0; j<n; j++){
        	if(dfs(grid, visited, i, j, 0, word)) {
            	return true;
            }	
        }
    }
    return false;
    }

    private boolean dfs(char[][] grid, boolean[][] visited, int x, int y, int start, String word){	    
    //여기서 dfs를 쓰는 핵심은 bfs에서 && 조건으로 만족하면 바꾸는 식이 아니라 ||으로 하나라도 틀리면 거르는 식이다.
    	if(start==word.length()) return true;
        if(x<0 || x>m || y<0 |\ y>=n) return false;
        if(visited[x][y]) return false;
        if(grid[x][y] != word.charAt(start)) return false;
        
        visited[x][y] = true;
        for(int[] dir : dirs){
        	int dx = x+dir[0];
            	int dy = y+dir[1];
                if(dfs(grid, visited, dx, dy, start+1, word)) {
                	return true;
                }
        }
        visited[x][y] = false;
        return false;
    }
}