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

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

코드

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    static class Point {
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public int solution(int[][] maps) {
        int n = maps[0].length;  // 가로 길이
        int m = maps.length;     // 세로 길이
        
        // 현재 위치 기준 상, 우, 하, 좌의 좌표
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

        // 다음으로 확인할 좌표 저장하는 큐
        Queue<Point> queue = new LinkedList<>();
        
        // 이동 거리를 저장하는 배열
        int[][] distance = new int[m][n];

        // 초기 설정
        queue.offer(new Point(0, 0));
        maps[0][0] = 0;
        distance[0][0] = 1;

        while (!queue.isEmpty()) {
            Point node = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nowX = node.x + dx[i];
                int nowY = node.y + dy[i];

                // 다음 칸으로 이동할 수 있을 때
                if (nowX >= 0 && nowX < m
                        && nowY >= 0 && nowY < n
                        && maps[nowX][nowY] == 1) {
                    // 현재 좌표로 다시 오지 않도록 0으로 설정
                    maps[nowX][nowY] = 0;
                    
                    // 이동 거리 1 추가
                    distance[nowX][nowY] = distance[node.x][node.y] + 1;
                    
                    // 현재 좌표를 큐에 추가
                    queue.offer(new Point(nowX, nowY));
                }
            }
        }

        int answer = distance[m - 1][n - 1];
        return answer != 0 ? answer : -1;
    }
}

풀이

캐릭터는 현재 좌표에서 상하좌우 중 한 칸만 움직일 수 있다. 칸의 값이 0이면 막혀서 못 움직이고, 1일 때에만 움직일 수 있다.

루프를 돌며 현재 위치에서 움직일 수 있는 좌표를 구한다. 이미 방문했던 위치로는 다시 가지 않도록 한다. 이동한 위치의 이동 거리로 이전 좌표의 이동 거리에 1을 더한다.

BFS는 노드를 레벨 순서대로 탐색하고, 큐를 사용한다. 따라서 어떤 노드에 처음 도달했을 때 그 경로는 최단 경로가 된다. 만약 다른 경로가 발견된다 하더라도 그것은 같은 레벨의 노드에서 이어진 것이다. 방문했던 노드는 다시 방문하지 않기 때문에 BFS는 최단 거리를 보장한다.