[LeetCode- Ch7. DFS & BFS] 7. 구슬 미로

https://www.lintcode.com/problem/787/

LintCode 炼码

 

---

BFS 기본 

1. 방향 설정 & 배열 사이즈 변수 설정
2. 맞는 조건 탐색
3. 큐 생성
4. 조건 체크해서 큐 넣기
   1. 마이너스 좌표 체크
   2. m*n 범위 체크
   3. grid[x][y]값 체크

 

---

문제 조건

1. 구슬은 벽이 없으면 한 방향으로 쭉 이동한다.

2. 이동한 다음에는 다른 방향으로 이동 가능하다.

3. 시작지점에서 목적지점까지 갈 수 있는지 여부 리턴

 

문제 풀이 순서 - BFS

1. Queue에서 poll 한후

2. 4방향으로 체크시작

3. 공식: 조건체크 부분 수행

4. (3,4)까지 도착한후 에러 체크 한다.

While문에 서 올린 좌표를 –로 원상복귀 visited[x][y]==true인지 체크 후 방문한적이 없으면 true 입력

5. queue.offer(2,4)

 

 

문제 풀이 순서 - DFS

1. Stack에 (0,4) push

2. 4방향으로 체크시작

3. 공식: 조건체크 부분 수행

4. (3,4)까지 도착한후 에러 체크 한다.

While문에 서 올린 좌표를 –로 원상복귀 visited[x][y]==true인지 체크 후 방문한적이 없으면 true 입력 

5. DFS(2,4)

 

1. BFS 이용

class Point{
    public int x,  y;
    Point(int x, int y){
        this.x=x;
        this.y=y;
    }
}

public class Solution {
    static int n,m;
    static boolean[][]check;
    public boolean hasPath(int[][] maze, int[] startpoint, int[] destination) {
        //1.ds
        Point start = new Point(startpoint[0], startpoint[1]);
        Point dest = new Point(destination[0], destination[1]);
        Queue<Point> q = new LinkedList<>();


        n=maze.length;
        m=maze[0].length;

        int[][] dis = {{0,1},{1,0},{-1,0},{0,-1}};
        check= new boolean[n][m];

        q.offer(start);
        while(!q.isEmpty()){
            Point point = q.poll();
            for(int i=0;i<4;i++){
                boolean flag=false;
                Point np = new Point(point.x+dis[i][0], point.y+dis[i][1]);
                if(BFS(np, maze)){
                    while(!flag){
                        np=new Point(np.x+dis[i][0], np.y+dis[i][1]);
                        if(!BFS(np, maze)) flag=true;
                    }
                    np=new Point(np.x-dis[i][0], np.y-dis[i][1]);
                    //isValid 메서드 사용하지 않는 이유 : check에 true처리하면 안되므로
                    if(np.x==dest.x&&np.y==dest.y) return true;
                    if(check[np.x][np.y]==false){
                    q.offer(np);
                    //벽에 부딪혔을 때, check에 true 처리
                    check[np.x][np.y]=true;
                    }
                    }
                }
            }
            return false;
        }
        
    
    public boolean BFS(Point point, int[][] maze){
        if(!isValid(point)|| maze[point.x][point.y]!=0){
            return false;
        }
        return true;
    }
    public boolean isValid(Point point){
        if(point.x<0 || point.y<0 || point.x>=n||point.y>=m) return false;
        return true;
    }
}

 

+) 세련된 풀이

public class Solution {
    static int[][] dis= {{-1,0},{1,0},{0,1},{0,-1}};
    static int n,m;
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        n=maze.length;
        m=maze[0].length;

        //에러 체크
        if(start[0]==destination[0] && start[1]==destination[1]) return true;
        boolean[][] visited =new boolean[n][m];

        //출발지점 세팅
        visited[start[0]][start[1]]=true;

        //1.ds
        Queue<int[]> q = new LinkedList<>();
        q.offer(start);

        //큐가 빌때까지 반복
        while(!q.isEmpty()){
            int[] point= q.poll();
            //0,4
            for(int[] add : dis){
                int x = point[0]+add[0];
                int y = point[1]+add[1];
                //구슬이 벽면까지 가는 반복문
                while(x>=0 && y>=0 && x<n && y<m && maze[x][y]==0){
                    x+=add[0]; 
                    y+=add[1];
                }
                //구슬이 벽면에 도달시 -1해서 좌표 변수 설정
                x-=add[0];
                y-=add[1];

                //구슬이 벽에 도달 시
                //1. 방문 여부 확인
                //2. 방문 했다고 체크
                //3. 도착지점인지 확인
                //4. 큐에 삽입

                if(visited[x][y]) continue;
                visited[x][y]=true;
                if(x==destination[0] && y==destination[1]) return true;
                q.offer(new int[]{x,y});
            }
        }
        return false;
    }
}

 

2. DFS 이용

class Point{
    public int x,  y;
    Point(int x, int y){
        this.x=x;
        this.y=y;
    }
}

public class Solution {
    static int n,m;
    static boolean[][]check;
    static boolean answer=false;
    static int[][] dis = {{0,1},{1,0},{-1,0},{0,-1}};

    public boolean hasPath(int[][] maze, int[] startpoint, int[] destination) {
        //1.ds
        Point start = new Point(startpoint[0], startpoint[1]);
        Point dest = new Point(destination[0], destination[1]);

        n=maze.length;
        m=maze[0].length;

        check= new boolean[n][m];
        return DFS(start, dest, maze);
    }
        
    
    public boolean DFS(Point point, Point dest,int[][] maze){
         if(dest.x==point.x&&dest.y==point.y){
            return true;
        }
        if(!isValid(point, maze)){
            return false;
        }
        check[point.x][point.y]=true;


        for(int i=0;i<4;i++){
            boolean flag=false;
            Point np=point;
            while(!flag){
                System.out.println(i);
                np=new Point(np.x+dis[i][0], np.y+dis[i][1]);
                if(np.x<0 || np.y<0 || np.x>=n||np.y>=m||maze[np.x][np.y]!=0) flag=true;
            }
            np=new Point(np.x-dis[i][0], np.y-dis[i][1]);
            if(DFS(np, dest, maze)) return true;
        }
        
        return false;
    }
    public boolean isValid(Point point,int[][] maze){
        if(point.x<0 || point.y<0 || point.x>=n||point.y>=m||maze[point.x][point.y]!=0 ||check[point.x][point.y]==true) return false;
        return true;
    }
}

 

+) 세련된 풀이

public class Solution {
    static int[][] dis= {{-1,0},{1,0},{0,1},{0,-1}};
    static int n,m;
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        n=maze.length;
        m=maze[0].length;

        //에러 체크
        if(start[0]==destination[0] && start[1]==destination[1]) return true;
        boolean[][] visited =new boolean[n][m];

        //출발지점 세팅
        visited[start[0]][start[1]]=true;
        
        //DFS 호출
        return DFS(maze, start, destination, visited);
    }
    public boolean DFS(int[][] maze, int[] start, int[] destination, boolean[][] visited){
	    //DFS의 경우 초기값부터 확인을 시작한다.
        //1. 방문 여부 확인
        //2. 방문했다고 체크
        //3. 도착지점인지 확인
        
        if(!isValid(start,maze)&& visited[start[0]][start[1]]==true){
            return false;
        }
        
        visited[start[0]][start[1]]=true;

        if(start[0]==destination[0]&& start[1]==destination[1]) return true;

        for(int[] add : dis){
            int x=start[0]+add[0];
            int y=start[1]+add[1];
            while(isValid(new int[]{x,y}, maze)){
                x+=add[0];
                y+=add[1];
            }
            x-=add[0];
            y-=add[1];
            System.out.println(start[0]+" "+start[1]+" "+x+" "+y);

            //구슬이 벽에 도달 시
            //1. 방문 여부 확인
            //2. 스택에 삽입
            if(visited[x][y]==true) continue;
            
            if(DFS(maze, new int[]{x,y}, destination, visited)) return true;
        }

        return false;
    }
    public boolean isValid(int[] point, int[][] maze){
        if(point[0]<0|| point[1]<0 || point[0]>=n || point[1]>=m || maze[point[0]][point[1]]==1){
            return false;
        }
        return true;
    }
}