프로그래머스 - 게임 맵 최단거리(Java)

 

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

 

BFS문제를 오랜만에 풀어서 어려웠다.

 

처음에는 DFS로 풀었다.

 

정확성 테스트는 모두 통과 했지만, 효율성 테스트에서 시간초과로 실패하였다.

 

<DFS>

import java.util.*;

class Solution {
    public boolean[][] visit;
    public int answer=2147483647;
    public int[] dx={-1,1,0,0};
    public int[] dy={0,0,-1,1};
    public boolean check=false;
    public int solution(int[][] maps) {
        visit=new boolean[maps.length][maps[0].length];
        move(maps,0,0,1);
        if(check==false){
            return -1;
        }
        return answer;
    }
    
    public void move(int[][] maps, int x, int y,int count){
             if(x==maps[0].length-1 && y==maps.length-1){
                 answer=Math.min(answer,count);
                 check=true;
                return;
             }
            if(x<0 || y<0 || x>=maps[0].length || y>=maps.length || maps[y][x]==0){
                return;
             }
        
        if(visit[y][x]){
            return;
        }
        visit[y][x] = true; 
        
        move(maps,x+1,y,count+1);
        move(maps,x,y+1,count+1);
        move(maps,x-1,y,count+1);
        move(maps,x,y-1,count+1);
        
        visit[y][x]=false;
        
        }
       
}

 

 

이유는 간단하다.

 

DFS는 모든 경로를 방문하면서 최단 경로를 구하지만,

 

BFS는 가장 먼저 반환하는 값이 최단 경로이기 때문에 모든 경로를 다 탐색 할 필요가 없다.

 

<BFS 코드>

import java.util.*;

class Solution {
    private static final int[] dx = {0, 0, -1, 1};
    private static final int[] dy = {-1, 1, 0, 0};
    
    public int solution(int[][] maps) {
        int n = maps.length;
        int m = maps[0].length;
        
        boolean[][] visited = new boolean[n][m];
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0, 1});
        visited[0][0] = true;
        
        while(!queue.isEmpty()){ 
            int[] current = queue.poll();
            int x = current[0];
            int y = current[1];
            int cnt = current[2];
            
            if(x == n-1 && y == m-1){
                return cnt; 
            }
            
            for(int i=0;i<4;i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if(nx >=0 && ny >= 0 && nx < n && ny < m && maps[nx][ny] == 1 && !visited[nx][ny]){
                    visited[nx][ny] = true;
                    queue.add(new int[]{nx, ny, cnt+1});
                }
            }
        }
        
        return -1;
    }
}