[백준] 2178번 (java 자바)

DFS로 풀다가 답이 안나왔다 

 

-> 모든 경우를 찾기 때문에 최단 경로 찾을 때 DFS는 적합하지 않음

import java.util.*;

public class Main
{
    static final int MAX_N = 1000;
    static int N, M;
    static int[][] Graph = new int[MAX_N][MAX_N];
    static int[][] D = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    static class Point {
        Point(int r, int c, int d){
            row = r; col = c; dist = d;
        }
        int row, col, dist;
    }
    
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		for(int i = 0; i < N; i++){
		    String str = sc.next();
		    for(int j = 0; j < M; j++){
		        Graph[i][j] = str.charAt(j) - '0';
		    }
		}
		
		System.out.println(dfs());
	}
	
	static int dfs(){
	    boolean[][] visited = new boolean[MAX_N][MAX_N];
        
	    Stack<Point> mystack = new Stack<>();
	    mystack.push(new Point(0, 0, 1));
	    visited[0][0] = true;
	    
	    while(!mystack.empty()){
	        Point curr = mystack.pop();
	        
	        if(curr.row == N-1 && curr.col == M-1) return curr.dist;
	        
	        
	        for(int i = 0; i < 4; i++){
	            int nr = curr.row + D[i][0]; int nc = curr.col + D[i][1];
	            if(nr < 0 || nr > N - 1 || nc < 0 || nc > M - 1) continue;
	            if(visited[nr][nc]) continue;
	            if(Graph[nr][nc] == 0) continue;
	            
	            visited[nr][nc] = true;
	            mystack.push(new Point(nr, nc, curr.dist + 1));
	        }
	       
	        }
	        return -1;
	    }
}

 

 

 

BFS 풀 경우 

 

import java.util.*;

public class Main
{
    static final int MAX_N = 1000;
    static int N, M;
    static int[][] Graph = new int[MAX_N][MAX_N];
    static int[][] D = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    static class Point {
        Point(int r, int c, int d){
            row = r; col = c; dist = d;
        }
        int row, col, dist;
    }
    
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		for(int i = 0; i < N; i++){
		    String str = sc.next();
		    for(int j = 0; j < M; j++){
		        Graph[i][j] = str.charAt(j) - '0';
		    }
		}
		
		System.out.println(bfs());
	}
	
	static int bfs(){
	    boolean[][] visited = new boolean[MAX_N][MAX_N];
        
	    Queue<Point> myqueue = new LinkedList<>();
	    myqueue.add(new Point(0, 0, 1));
	    visited[0][0] = true;
	    
	    while(!myqueue.isEmpty()){
	        Point curr = myqueue.remove();
	        
	        if(curr.row == N-1 && curr.col == M-1) return curr.dist;
	        
	        
	        for(int i = 0; i < 4; i++){
	            int nr = curr.row + D[i][0]; int nc = curr.col + D[i][1];
	            if(nr < 0 || nr > N - 1 || nc < 0 || nc > M - 1) continue;
	            if(visited[nr][nc]) continue;
	            if(Graph[nr][nc] == 0) continue;
	            
	            visited[nr][nc] = true;
	            myqueue.add(new Point(nr, nc, curr.dist + 1));
	        }
	       
	        }
	        return -1;
	    }
}

왜 틀리지