[프로그래머스] 게임 맵 최단거리 (자바)

게임 맵 최단거리

문제풀이

해당 문제는 좌표를 지나면서 최단 거리를 찾는 문제입니다.
최단 거리를 찾기 위해서는 DFS 방식보다는 BFS 방식을 사용하는 것이 시간초과 오류를 방지할 수 있는 방법입니다.

저는 Point 클래스를 만들어줘서 해당 좌표 x,y값과 해당 좌표에서의 지나온 거리 횟수 값을 가지도록 설계했습니다.

그 뒤로 Queue를 이용한 BFS 방식을 사용했습니다. Queue의 타입은 제가 만들었던 Point 클래스로 했고 dx배열과 dy배열을 선언해서 반복문을 사용하여 동,서,남,북으로 좌표를 이동하는 것을 구현했습니다.
그 이후로는 기본적인 BFS 방식을 그대로 사용하시면 됩니다. visit 배열이 false이고 해당 map 배열의 좌표로 이동할 수 있다면 큐에 Point 객체를 넣고 Point 객체의 count값은 +1을 해서 추가합니다. 그리고 visit 배열은 true로 설정하면 됩니다.

구현코드

import java.util.*;
class Solution {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static boolean[][] visit;
    static int min = Integer.MAX_VALUE;
    static int answer = -1;
    
    class Point{
        int x;
        int y;
        int count;
        
        Point(int x, int y, int count){
            this.x = x;
            this.y = y;
            this.count = count;
        }
    }
    
    public int solution(int[][] maps) {
        // int answer = 0;
        visit = new boolean[maps.length][maps[0].length];
        
        bfs(maps);
        if(min == Integer.MAX_VALUE){
            return -1;
        }
        else{
            return min;    
        }
    }
    
    
    public void bfs(int[][] maps){
        Point point = new Point(0,0,1);
        
        Queue<Point> queue = new LinkedList<>();
        
        queue.add(point);
        visit[0][0] = true;
        
        while(!queue.isEmpty()){
            Point curPoint = queue.poll();
            // visit[curPoint.x][curPoint.y] = true;
            
            if(curPoint.x == maps.length-1& curPoint.y == maps[0].length-1){
                if(min > curPoint.count){
                    min = curPoint.count;
                }
            }
            
            for(int i =0; i<4; i++){
                int nx = dx[i] + curPoint.x;
                int ny = dy[i] + curPoint.y;
                
                if(nx<0 || ny<0 || nx>=maps.length || ny>=maps[0].length){
                    continue;
                }
                
                if(visit[nx][ny] == false && maps[nx][ny]==1){
                    queue.add(new Point(nx,ny,curPoint.count+1));
                    visit[nx][ny] = true;

                    // System.out.println("nx,ny : "+nx+","+ny+","+curPoint.count);

                }
                
            }
            
        }
        
        
    }
}

주로 최단 거리 문제들에 BFS 방식이 많이 쓰이니까 같은 유형의 문제를 풀어보면서 BFS를 연습하는 것도 좋을거 같습니다!