코드트리 [자바 java] 네 방향 탈출 가능 여부 판별하기

https://www.codetree.ai/missions/2/problems/determine-escapableness-with-4-ways?utm_source=clipboard&utm_medium=text

 

 

https://ethereal-coder.tistory.com/86

코드트리 [자바 java] 두 방향 탈출 가능 여부 판별하기

 

두방향 탈출여부 판별과 거의 유사한 문제이다.

마찬가지로 0,0부터 탐색하기 시작해서 상하좌우에 뱀이 없는 칸을 queue에 넣어 다시 그 칸에 대한 상하좌우를 탐색하도록 하였다. 이때 특정 칸에 대해서 끝 도달 가능 여부는 정해져 있기 때문에 이미 탐색한 칸을 또 탐색하면 효율만 떨어져서 vis 배열을 이용해서 방문여부를 표시했다.

달라진 점은 방향이 상우에서 상하좌우로 바뀌었다는 것과, bfs로 풀어야한다는 점이다.

나는 dx,dy 배열에 -1요소를 추가하고, stack를 queue로 바꾸었다. 

 

import java.io.*;
import java.util.*;


public class Main {

    static class xy{
        int x;
        int y;
        xy(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException{
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       StringTokenizer st = new StringTokenizer(br.readLine());

       int n = Integer.parseInt(st.nextToken());
       int m = Integer.parseInt(st.nextToken());

       int[][] arr = new int[n][m];

       for(int i =0;i<n;i++){
        st = new StringTokenizer(br.readLine());
        for(int j =0 ;j<m;j++){
            arr[i][j] = Integer.parseInt(st.nextToken());
        }
       }

       Queue<xy> q = new LinkedList<>();

       q.offer(new xy(0,0));

       int[] dx = {1,0,-1,0};
       int[] dy = {0,1,0,-1};

       boolean[][] vis = new boolean[n][m];

       while(q.isEmpty() != true){
        xy now = q.poll();

        if(now.x == n-1 && now.y == m-1){
            System.out.println(1);
            System.exit(0);
        }

        if(vis[now.x][now.y] == false){
            vis[now.x][now.y] = true;
            for(int i = 0;i<4;i++){
            if( now.x + dx[i] < n && now.x + dx[i] >=0 && now.y + dy[i] < m && now.y + dy[i] >=0 &&arr[now.x + dx[i]][now.y + dy[i]] == 1){
                q.offer(new xy(now.x + dx[i], now.y + dy[i]));
            }
        }

        }

       }

       System.out.println(0);
    }
}