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

문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

 

[ 접근 방법 ]

목적지를 향해 2차원 배열이 주어졌을 때의 최단 거리를 묻는 문제이다.

정확히 2차원 배열이 주어졌고 다음 거리까지의 가중치가 없다.

-> BFS를 통해 구할 수 있는 문제라고 판단

 

1. BFS 방식으로 구하기 위해 Queue를 생성하고 첫 시작점을 Queue에 넣는다

  1-1. 이때 좌표(row, col)을 넣어야 함으로 원소가 두 개 들어갈 수 있는 배열 혹은 class를 사용한다

2. Queue에서 값을 뽑고 이동할 수 있는 곳 중 갈 수 있는 곳을 찾아 큐에 넣는다

  2-1. 이동할 수 있는 좌표를 구하기 위한 move 배열을 선언해 놓는 게 편하다.

  2-2. validation 로직으로 map 배열의 범위를 넘거나, 이미 방문을 한 곳이거나(isVisited 배열 확인), 갈 수 없는 길(map 상에 0으로 표시된 곳)을 필터링한다.

  2-3. 방문할 수 있는 곳은 Queue에 넣고, isVisited에 방문했다는 표시를 해주며, 현재까지 온 거리를 map 배열에 업데이트 해준다.

3. 다음 위치로 나아갈 때마다 map 상에 현재까지 온 거리를 저장한다.

4. 최종 결과를 반환하는 방식

  4-1. 만약 다음에 나온 곳이 최종 목적지이면 바로 이전에 온 거리에서 +1을 해서 return 한다

  4-2. 전체 탐색이 끝나고 BFS를 구하기 위해 넣은 큐에 값도 없다면 해당 장소까지 갈 수 있는 방법이 없다고 판단해 -1을 return 한다.

 

[ 코드 ]

import java.util.ArrayDeque;
import java.util.Queue;

public class Solution {

    private static int [][] move = {{0,-1}, {-1, 0}, {0, 1}, {1, 0}};

    public int solution(int[][] maps) {
        boolean [][] isVisited = new boolean[maps.length][maps[0].length];
        Queue<Location> queue = new ArrayDeque<>();
        Location location = new Location(0, 0);
        queue.add(location);
        isVisited[0][0] = true;

        while(!queue.isEmpty()){
            Location poll = queue.poll();
            for(int i = 0; i < move.length; i++) {
                int newRow = poll.row + move[i][0];
                int newCol = poll.col + move[i][1];
                if (validate(newRow, newCol, maps) && !isVisited[newRow][newCol]){
                    if(newRow == maps.length -1 && newCol == maps[0].length -1){
                        return maps[poll.row][poll.col] + 1;
                    }
                    Location newLocation = new Location(newRow, newCol);
                    queue.add(newLocation);
                    isVisited[newLocation.row][newLocation.col] = true;
                    maps[newLocation.row][newLocation.col] = maps[poll.row][poll.col] + 1;
                }
            }
        }

        return -1;
    }

    private boolean validate(int newRow, int newCol, int [][] maps) {
        if(newRow < 0 || newRow > maps.length -1 || newCol < 0 || newCol > maps[0].length -1){
            return false;
        }

        if(maps[newRow][newCol] == 0){
            return false;
        }

        return true;
    }

    class Location{
        int row;
        int col;
        public Location(int row, int col){
            this.row = row;
            this.col = col;
        }
    }

}