[JAVA] 프로그래머스 : 게임 맵 최단거리

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

이 문제는 최단 거리를 찾는 문제이다. 최단 거리를 찾으려면 bfs(너비 우선 탐색) 알고리즘을 사용하면 된다. 이 문제를 풀며 어려웠던 점은 '큐 안에 배열을 넣는다'였다. 즉, 큐 안에다가 x,y좌표를 넣어 푸는 것이다.

우선, 상하좌우를 탐색할 배열을 전역변수로 선언 및 초기화 해 준다. 이는 현재 x,y 좌표에 배열 요소를 하나씩 더해 줌으로써 구현할 수 있다.

예를 들어 int[] dx = {0,0,-1,1}를 보면, '현재 x좌표 + dx의 요소'를 for문을 돌려 반복해 주면 되는 것이다.

이후 조건문을 통하여 큐에 저장해 주면 된다.

import java.util.*;

class Solution {
    //{상,하,좌,우}
    private static int[] dx = {0,0,-1,1}; //좌,우는 x의 이동
    private static int[] dy = {1,-1,0,0}; //상,하는 y의 이동
    public int solution(int[][] maps) {
        int n = maps.length; //가로 칸의 개수
        int m = maps[0].length; //세로 칸의 개수
        int[][] distance = new int[n][m]; //최단 거리를 저장할 배열
        boolean[][] visited = new boolean[n][m]; //방문 여부를 저장할 배열
        
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0}); // 시작점 추가
        visited[0][0] = true;
        distance[0][0] = 1; // 시작점까지의 거리는 1
        
        while(!queue.isEmpty()){
            int[] now = queue.poll();
            int x = now[0]; //x좌표
            int y = now[1]; //y좌표
            
            for(int i=0; i<4; i++){
                int newX = x + dx[i];
                int newY = y + dy[i];
                
                if(newX >= 0 && newY >= 0 && newX < n && newY < m && maps[newX][newY] == 1 && visited[newX][newY] == false){
                    queue.add(new int[]{newX, newY});
                    visited[newX][newY] = true;
                    distance[newX][newY] = distance[x][y] + 1; //거리 1 증가
                }
            }
        }
        if(distance[n-1][m-1] == 0){
            return -1;
        } else {
            return distance[n-1][m-1];
        }
    }
}