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

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

프로그래머스

 

미로 게임이랑 거의 유사하지만 만약 가는 길이 없으면 가장 마지막에 -1로 출력해야되는 부분이 달랐다. 최단 거리를 구하는 문제이기 때문에 bfs를 구현해서 풀면 됐었는데, bfs의 for문 내에서 queue에 값을 추가해야하는 것을 까먹고 재귀로 넣어서 첫 번째 풀이는 틀렸었다. 탐색을 시작하는 지점은 (0, 0) 좌표이기 때문에 애초에 bfs(0, 0)을 실행하면 된다. visited[0][0]은 bfs 함수를 처음 실행하기 전에 true로 만들어주고 bfs 내부에서 방문할 때 true로 바꿔주면 된다.

 

+ 제한사항에 maps의 크기가 n*m이라고 되어있는데 n과 m이 같을 수도, 다를 수도 있다고 되어있기 때문에 이를 유의하여 visited 배열을 만들어야함! (24.10.17 수정)

 

import java.util.*;

class Solution {
    public static int[][] visited;
    public static int[] dx = {1, -1, 0, 0};
    public static int[] dy = {0, 0, 1, -1};
    public int solution(int[][] maps) {
        visited = new int[maps.length][maps[0].length];
        bfs(0, 0, maps);
        int answer = visited[maps.length-1][maps[0].length-1];
        if(answer == 0) answer = -1;
        return answer;
    }
    public static void bfs(int a, int b, int[][] maps){
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{a, b});
        visited[a][b] = 1;
        
        while(!queue.isEmpty()){
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            
            for(int i = 0; i < 4; i++){
                int next_x = x + dx[i];
                int next_y = y + dy[i];
                
                if(next_x >= 0 && next_y >= 0 && next_x < maps.length && next_y < maps[0].length){
                    if(visited[next_x][next_y] == 0 && maps[next_x][next_y] == 1){
                        visited[next_x][next_y] = visited[x][y] + 1;
                        queue.add(new int[]{next_x, next_y});
                    }
                }
            }
        }
        
    }
}