게임 맵 최단거리

문제

(0,0) 지점에서 (n,m) 지점까지 가는 최단거리를 구하는 문제이다. 종점에 도달하지 못하는 경우에는 -1을 출력한다.
효율성 체크를 하기 때문에 BFS로 풀어야한다 ;;

풀이

DFS 풀이

class Solution {
    static int[] dx = {0,1,0,-1};
    static int[] dy = {1,0,-1,0};
    static int answer=Integer.MAX_VALUE;
    static int[][] ch;
    
    public static void DFS(int L,int x,int y,int[][] maps,int n,int m,int[][] ch){
        if(x==(n-1) && y==(m-1)) answer = Math.min(answer,L);
        else{  
            for(int i=0; i<4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx>=0 && nx<n && ny>=0 && ny<m && maps[nx][ny]==1 && ch[nx][ny]==0){
                    ch[nx][ny]=1;
                    DFS(L+1,nx,ny,maps,n,m,ch);
                    ch[nx][ny]=0;
                }
            }
        }
    }
    
    public int solution(int[][] maps) {      
        int n = maps.length;
        int m = maps[0].length;
        
        ch = new int[n][m];
        ch[0][0]=1;
        
        DFS(0,0,0,maps,n,m,ch);
        
        if(answer==Integer.MAX_VALUE) return answer = -1;
        else return answer+1;
    }
}

처음에는 효율성테스트 같은 거 있는 줄 모르고 DFS로도 풀 수 있어서 DFS로 도전했다.
재귀호출이 끝나면 빽트래킹 후에 뒤로 되돌아가서 4가지 방향대로 다시 재귀를 시작하면서 다른 방향으로 나아간다. 애초에 테스트 케이스가 속도 좋게 다 성공했다.
근데 프로그래머스에는 효율성 테스트가 있네? 그래서 기존의 maps배열을 방문했으면 0으로 바꾸는 방식에서 방문체크배열 ch를 넣었다. 그래도 안됨. 이유는 최단거리를 찾기위해서 끝에 도달했어도 다른 경로를 한번 가봐야한다. 그래서 효율성에서 안된다. 애초에 DFS/BFS 시작을 잘 해야한다.
그래서 BFS로 시작.

BFS 풀이

import java.util.*;

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

class Solution {
    static int[] dx ={0,1,0,-1};
    static int[] dy ={1,0,-1,0};
    static int[][] dis; //거리배열 역할

    public static void BFS(int x,int y,int[][] maps,int n,int m){
        Queue<Point> Q = new LinkedList<>();
        Q.offer(new Point(x,y));
        
        while(!Q.isEmpty()){
            Point tmp = Q.poll();
            for(int i=0; i<4; i++){
                int nx = tmp.x + dx[i];
                int ny = tmp.y + dy[i];
                if(nx>=0 && nx<n && ny>=0 && ny<m && maps[nx][ny]==1){
                    maps[nx][ny]=0;
                    Q.offer(new Point(nx,ny));
                    dis[nx][ny]=dis[tmp.x][tmp.y]+1;
                }
            }
        }
        
    }
    
    
    public int solution(int[][] maps) {
        int answer = 0;
        int n = maps.length;
        int m = maps[0].length;
        
        dis = new int[n][m];
        BFS(0,0,maps,n,m);
        
        if(dis[n-1][m-1]==0) return -1;
        else return dis[n-1][m-1]+1;
    }
}

원리는 DFS랑 비슷한데, DFS가 한 길로 간다면 BFS는 한칸씩 지날때마다 갈수있는 모든 경로를 한방에 다 같이 나아간다고 생각하면된다. 그렇게 나아갈때마다 전 단계 거리에서 +1씩 해준다.
그렇게 종점에 도달했을 때의 값이 자연스레 제일 최단거리 값이 들어오게 된다.