[프로그래머스][JAVA] 게임 맵 최단거리 (BFS(o), DFS(x))

BFS로 풀어야 하는 문제라고 한다..

 

 

import java.util.*;
 
class Solution {
    private static int[] dr = {0, 1, 0, -1};
    private static int[] dc = {1, 0, -1, 0};
    private static boolean[][] visited;
    private static int n, m;
    
    public int solution(int[][] maps) {
        n= maps.length;
        m= maps[0].length;
        visited = new boolean[n][m];
        return BFS(0, 0, maps);
    }
    
    private int BFS(int r, int c, int[][] maps){
        Queue<Coordinate> q = new LinkedList<>();
        q.offer(new Coordinate(r, c, 1));
        visited[r][c] = true;
        
        while(!q.isEmpty()){
            Coordinate coord = q.poll();
            if(coord.r == n-1 && coord.c == m-1) return coord.moveNum;
            
            for(int i=0; i<4; i++){
                int nr = coord.r + dr[i];
                int nc = coord.c + dc[i];
                
                if(0<=nr && nr<n && 0<=nc && nc<m){
                    if(maps[nr][nc]==1 && !visited[nr][nc]){
                        q.offer(new Coordinate(nr, nc, coord.moveNum+1));
                        visited[nr][nc] = true;
                    }
                }
            }
            
        }
        return -1;
    }
    
    private class Coordinate{
        int r;
        int c;
        int moveNum;
        
        public Coordinate(int r, int c, int moveNum){
            this.r = r;
            this.c = c;
            this.moveNum = moveNum;
        }
    }
}

 

 

 

import java.util.*;
 
class Solution {
    int[] dx = {0, 1, 0, -1};
    int[] dy = {-1, 0, 1, 0};
    boolean[][] visited;
    int n, m;
    public int solution(int[][] maps) {
        n = maps.length;
        m = maps[0].length;
        visited = new boolean[n][m];
        return bfs(0, 0, maps);
    }
    
    public int bfs(int x, int y, int[][] maps){
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(x,y,1));
        visited[x][y] = true;
        
        while(!q.isEmpty()){
            Node node = q.poll();
            if(node.x == n-1 && node.y == m-1) return node.cost;
            for(int i=0; i<4; i++){
                int nx = node.x + dx[i];
                int ny = node.y + dy[i];
                
                if(0<=nx && nx<n && 0<=ny && ny<m){
                    if(maps[nx][ny]==1 && !visited[nx][ny]){
                        visited[nx][ny] = true;
                        q.offer(new Node(nx,ny, node.cost+1));
                    }
                }
                
            }
        }
        return -1;
    }
    
    public class Node {
        int x;
        int y;
        int cost;
        
        public Node(int x, int y, int cost) {
            this.x = x;
            this.y = y;
            this.cost = cost;
        }
    }
}

 

 

 

DFS로 하면

import java.util.*;
 
class Solution {
    private static int[] dr = {0, 1, 0, -1};
    private static int[] dc = {1, 0, -1, 0};
    private static int[][] dp;
    
    public int solution(int[][] maps) {
        int answer = 0;
        dp = new int[maps.length][maps[0].length];
        for(int i=0; i<maps.length; i++){
            Arrays.fill(dp[i], maps.length*maps[0].length+1);    
        }
        find(maps, 0, 0, 1);
        // System.out.println(dp[maps.length-1][maps[0].length-1]);
        answer = dp[maps.length-1][maps[0].length-1];
        answer = (answer<maps.length*maps[0].length+1)? answer : -1;
        
        return answer;
    }
    
    private void find(int[][] maps, int r, int c, int moveNum){
        if(r==maps.length-1 && c==maps[0].length-1){
            dp[r][c] = Math.min(dp[r][c],moveNum);
            return;
        }
        
        for(int i=0; i<4; i++){
            int nr = r+dr[i];
            int nc = c+dc[i];
            if(0<=nr && nr<maps.length 
                && 0<=nc && nc<maps[0].length 
                && maps[nr][nc]==1 && moveNum+1<dp[nr][nc]){
                // System.out.println(nr+" "+nc+" "+moveNum);
                dp[nr][nc] = moveNum+1;
                find(maps, nr, nc, moveNum+1);
            }       
        }   
    }
}

효율성 1,3,4 실패