[JAVA] 게임 맵 최단거리 - 프로그래머스[Lv.2]

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

프로그래머스

---

import java.util.*;
class Solution {
    static int n, m, nx, ny;
    static int[][] move = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
    static int[][] answer;
    public int solution(int[][] maps) {
        n = maps.length;
        m = maps[0].length;
        answer = new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(answer[i], Integer.MAX_VALUE);
        }
        answer[0][0] = 1;
        bfs(maps);
        return answer[n-1][m-1] == Integer.MAX_VALUE ? -1 : answer[n-1][m-1]; //최소 2칸 필요
    }
    public void bfs(int[][] maps) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0});
        while(!queue.isEmpty()){
            int[] now = queue.poll();
            if(now[0] == n-1 && now[1] == m-1) continue;
            for(int[] d : move){
                nx = now[0] + d[0];
                ny = now[1] + d[1];
                if(nx < 0 || nx >= n || ny < 0 || ny >= m || maps[nx][ny] == 0) continue;
                if(answer[now[0]][now[1]] + 1 < answer[nx][ny]){
                    answer[nx][ny] = answer[now[0]][now[1]] + 1;
                    queue.add(new int[]{nx, ny});
                }
            }
        }
    }
}

💡 BFS

풀이

• BFS로 진행해주되, answer 배열을 따로 만들어 maps[i][j]에 도달할 때 가능한 최소 거리값을 갱신해나감
  • maps에 바로 갱신하면 되돌아가서 무한 반복에 빠질 수 있으므로 그냥 answer배열 별도로 생성함
  • answer[0][0]을 제외한 나머지 값을 MAX_VALUE로 초기화
  • 현재 answer+1 이 answer[nx][ny] 보다 작은 경우 갱신함

구현은 간단한데 생각보다 시간을 많이 잡아먹음;;; 상대 진영에 도달하지 못하는 경우 체크하는데서 애먹었다
처음엔 answer[n-1][m-1] 값이 1 이하인지 비교해서 1 이하인 경우 도달하지 못했다고 취급해서 -1리턴함 (최소 2칸 이상의 map이 주어지므로) ..가 아니라 그냥 초기값에서 갱신됐는지 체크하면 된다
-.. 걍 바보였음 answer 전부 MAX_VALUE로 초기화 해놓고;;; 올해의 노벨 바보상 수상....ㅋ^^ 아 땡큐