[DFS] 두 방향 탈출 가능 여부

import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;

public class Main {

    //길표시 grid랑 방문했는지 여부를 알릴 2차원배열 필요
    public static int[][] grid;
    public static int[][] visited;

    public static int N,M;

    public static int x = 0, y = 0;

    public static int newX, newY;

    public static int result = 0;

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

        N = parseInt(st.nextToken());
        M = parseInt(st.nextToken());
        grid = new int[N][M];
        visited = new int[N][M];


        //GRID랑 VISITED 생성
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++){
                grid[i][j] = parseInt(st.nextToken());
            }
        }

        visited[0][0] = 1;
        DFS(0,0);
        System.out.println(result);
    }

    public static void DFS(int x, int y){
        int[] dx = new int[] {0,1};
        int[] dy = new int[] {1,0};

        for(int i = 0; i < 2; i++){
            newX = x + dx[i];
            newY = y + dy[i];
            if(newX == N-1 && newY == M-1){
                result++;
                return;
            }
            if(CanGo(newX, newY)){
                visited[newX][newY] = 1;
                DFS(newX, newY);
            }
        }
    }

    // 뱀이 있는지, 격자를 벗어나진 않는지, 이미 지나온 곳인지 확인 필요
    public static boolean CanGo(int newX, int newY){
        if(newX < 0 || newX == M || newY < 0 || newY == N){
            return false;
        }else if(grid[newX][newY] == 0 || visited[newX][newY] == 1)
            return false;
        return true;
    }

}

• 위와 같이 모두가 1인 문제에서 count가 2가되는 문제가 발생했다. 문제의 원인은 오른쪽으로 이동이 먼저 그 다음 아래쪽 이동인데 목적지에 이르른 후 재귀과정에서 또다시 밑으로 이동하여 목적지에 한 번 더 도달하는 것이 문제였다.
• 그러므로 이미 목적지에 도달했을 때는 밑으로 가지 않도록 함수를 작성하였다.

import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;

public class Main {

    //길표시 grid랑 방문했는지 여부를 알릴 2차원배열 필요
    public static int[][] grid;
    public static int[][] visited;

    public static int N,M;

    public static int x = 0, y = 0;

    public static int newX, newY;

    public static int result = 0;

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

        N = parseInt(st.nextToken());
        M = parseInt(st.nextToken());
        grid = new int[N][M];
        visited = new int[N][M];


        //GRID랑 VISITED 생성
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++){
                grid[i][j] = parseInt(st.nextToken());
            }
        }

        visited[0][0] = 1;
        DFS(0,0);
        System.out.println(result);
    }

    public static void DFS(int x, int y){
        int[] dx = new int[] {0,1};
        int[] dy = new int[] {1,0};

        for(int i = 0; i < 2; i++){
            newX = x + dx[i];
            newY = y + dy[i];
            if(newX == N-1 && newY == M-1){
                result++;
                return;
            }
            
            //이미 목적지 도달하면 밑으로 이동x
            if(i == 1 && result == 1){
                return;
            }
            if(CanGo(newX, newY)){
                visited[newX][newY] = 1;
                DFS(newX, newY);
            }
        }
    }

    // 뱀이 있는지, 격자를 벗어나진 않는지, 이미 지나온 곳인지 확인 필요
    public static boolean CanGo(int newX, int newY){
        if(newX < 0 || newX == N || newY < 0 || newY == M){
            return false;
        }else if(grid[newX][newY] == 0 || visited[newX][newY] == 1)
            return false;
        return true;
    }

}

• 너무 복잡해졌나해서 다른 사람 코드 확인 중에 목적지에서 visited가 1이면 1을 출력하는 코드가 있어 따라해봤는데 그러면 모든 칸을 거쳐가므로 함수결과는 같지만 수행시간이 더 늘어났다.