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

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

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

dfs를 이용해서 탈출 가능 여부를 판단하는 문제이다.

0,0에서 출발해서 오른쪽, 아래로 갈 수 있는 길이 있는지 하나씩 탐색한다. 만약 갈 수 있다면, stack에 넣고 다시 그 위치에 대한 오른쪽, 아래를 탐색한다.

 

위와 오른쪽의 격자를 탐색하기 위해 dx,dy테크닉을 사용했고, 위, 왼쪽으로는 갈 수 없으니 -1요소는 넣지 않았다. 

나는 처음에 위, 왼쪽방향도 가능한 줄 알고, vis boolean배열을 이용해서 방문여부를 표시해주었다. 특정 위치에서 끝까지 갈 수 있는지의 여부는 오직 한가지이기 때문이다.

 

또한 처음에 런타임에러가 나왔는데, 이는 시스템을 종료하는 과정에서 System.exit(0)이 아닌 System.exit(1)을 써서 나오는 문제였다. 앞으로 꼭 주의해야겠다.

 

그리고 요즘에 격자문제를 풀 때 행과 열의 길이가 다른 경우 n과 m을 사용하는데에 실수가 많은 것 같다(특히 for문에서) 정말 조심해야겠다.

 

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());
        }
       }

       Stack<xy> s = new Stack<>();

       s.push(new xy(0,0));

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

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

       while(s.isEmpty() != true){
        xy now = s.pop();

        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<2;i++){
            if( now.x + dx[i] < n &&  now.y + dy[i] < m && arr[now.x + dx[i]][now.y + dy[i]] == 1){
                s.push(new xy(now.x + dx[i], now.y + dy[i]));
            }
        }

        }

       }

       System.out.println(0);
    }
}