[LeetCode- Ch7. DFS & BFS] 5. 단어 검색 #

 

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

Word Search - LeetCode

 

 

1. 원하는 단어를 배열에서 한줄로 이어진 상태로 찾으면 true 리턴

2. DFS를 이용

: 좌표, visited, word

 

 

1. 타임리밋 발생

class Point{
    public int x,y;
    Point(int x, int y){
        this.x=x;
        this.y=y;
    }
}
class Solution {
    static boolean [][] check;
    static int n,m,N;
    static int[][] dis={{1,0},{0,1},{-1,0},{0,-1}};
    static boolean flag;
    public boolean exist(char[][] board, String word) {
        n=board.length;
        m=board[0].length;
        check=new boolean[n][m];
        flag=false;
        
        N=word.length();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                Point point =new Point(i,j);
                //System.out.println(word.charAt(0)+" "+board[point.x][point.y]);
                if(board[point.x][point.y]==word.charAt(0) && check[point.x][point.y]==false){
                check[point.x][point.y]=true;
                DFS(point, board,1, word);
                check[point.x][point.y]=false;
            }
        }
        }
        
        return flag;
    }
    public boolean isValid(Point point){
        int x=point.x;
        int y=point.y;
        if(x<0 || y<0 || x>=n || y>=m) return false;

        return true;
    }
    public void DFS(Point point, char[][] board,int L, String word){
        if(L==N){
          //System.out.println("왔니");
            flag=true;
            return;
        }
  
        for(int i=0;i<4;i++){
            
            Point np= new Point(point.x+dis[i][0], point.y+dis[i][1]);
            //System.out.println(L+" "+np.x+" "+np.y);

            if(isValid(np)&&board[np.x][np.y]==word.charAt(L) && check[np.x][np.y]==false){
                System.out.println(L+" "+N+" "+np.x+" "+np.y);
                check[np.x][np.y]=true;
                DFS(np, board, L+1, word);
                check[np.x][np.y]=false;
            }
            //System.out.println();
        }
    }
}

 

2. 단어 뒤부터 돌려도 타임리밋 발생

class Point{
    public int x,y;
    Point(int x, int y){
        this.x=x;
        this.y=y;
    }
}
class Solution {
    static boolean [][] check;
    static int n,m,N;
    static int[][] dis={{1,0},{0,1},{-1,0},{0,-1}};
    static boolean flag;
    public boolean exist(char[][] board, String word) {
        n=board.length;
        m=board[0].length;
        check=new boolean[n][m];
        flag=false;
        
        N=word.length();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                Point point =new Point(i,j);
                //System.out.println(word.charAt(0)+" "+board[point.x][point.y]);
                if(board[point.x][point.y]==word.charAt(N-1) && check[point.x][point.y]==false){
                check[point.x][point.y]=true;
                if(N-1==0) return flag=true;
                else DFS(point, board,N-2, word);
                check[point.x][point.y]=false;
            }
        }
        }
        
        return flag;
    }
    public boolean isValid(Point point){
        int x=point.x;
        int y=point.y;
        if(x<0 || y<0 || x>=n || y>=m) return false;

        return true;
    }
    public void DFS(Point point, char[][] board,int L, String word){
        if(L==0){
          //System.out.println("왔니");
            flag=true;
            return;
        }
  
        for(int i=0;i<4;i++){
            
            Point np= new Point(point.x+dis[i][0], point.y+dis[i][1]);
            //System.out.println(L+" "+np.x+" "+np.y);

            if(isValid(np)&&board[np.x][np.y]==word.charAt(L) && check[np.x][np.y]==false){
                System.out.println(L+" "+N+" "+np.x+" "+np.y);
                check[np.x][np.y]=true;
                DFS(np, board, L-1, word);
                check[np.x][np.y]=false;
            }
            //System.out.println();
        }
    }
}

 

3. 처음 시작할 때 돌리면서 참 거짓 체크

class Point{
    public int x,y;
    Point(int x, int y){
        this.x=x;
        this.y=y;
    }
}
class Solution {
    static boolean [][] check;
    static int n,m,N;
    static int[][] dis={{1,0},{0,1},{-1,0},{0,-1}};
    static boolean flag;
    public boolean exist(char[][] board, String word) {
        n=board.length;
        m=board[0].length;
        check=new boolean[n][m];
        flag=false;
        
        N=word.length();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                Point point =new Point(i,j);
                if(DFS(point, board, 0, word)) return true;
            }
        }
        return false;
    }
    public boolean isValid(Point point){
        int x=point.x;
        int y=point.y;
        if(x<0 || y<0 || x>=n || y>=m) return false;

        return true;
    }
    public boolean DFS(Point point, char[][] board,int L, String word){
        if(L==word.length()){
            return true;
        }else if(!isValid(point)||board[point.x][point.y]!=word.charAt(L) || check[point.x][point.y]==true){
            return false;
        }
        check[point.x][point.y]=true;
        for(int i=0;i<4;i++){
            Point np= new Point(point.x+dis[i][0], point.y+dis[i][1]);
            if(DFS(np, board, L+1, word)) return true;
        }
        check[point.x][point.y]=false;
        return false;
    }
}