[PGM_1844] 게임 맵 최단거리 (java)

문제링크

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

코딩테스트 연습 - 게임 맵 최단거리

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 BFS

1. 문제 이해

(0,0)을 시작점으로 하여 정 반대편에 위치한 (n,m)으로 이동하는 최단거리를 구하는 문제이다. 입력으로 이동할 수 있는지 없는지의 여부의 map이 주어진다. 만약 (n,m)으로 이동할 수 없는 경우에는 -1을 return하여주면 된다.

 

2. 접근방법

최단거리를 구하는 방법으로 BFS를 선택하였다. 브루트포스로 완전탐색도 가능하지만 이것은 매우 비효율적이기 때문에 한번씩만 정점들을 확인하여 최단거리를 알 수 있는 BFS를 사용해주었다.

BFS 참고 -> 2021.12.14 - [CordingTest/Algolithm] - 그래프란? 그래프 탐색알고리즘(DFS,BFS) 

 

3. 세부 해결방안

while (!queue.isEmpty()){
    int[] position = queue.remove();
    for(int i = 0; i < 4; i ++){
        int x = position[0] + dx[i];
        int y = position[1] + dy[i];
        if(isOk(x,maps.length) && isOk(y,maps[0].length) && !checked[x][y] && maps[x][y] != 0){
            queue.add(new int[]{x,y});
            checked[x][y] = true;
            shortestLoad[x][y] = shortestLoad[position[0]][position[1]] + 1;
        }
    }
}

queue에 0,0에 대한 정보를 넣어줌으로써 bfs가 시작된다. 이동할 수 있는 상하좌우의 정점 중 체크하지 않은 정점에 Queue를 활용하여 탐색을 하며 BFS를 수행한다.

구현코드

package pgm_1844;

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

public class Solution {
    public int solution(int[][] maps) {
        boolean[][] checked = new boolean[maps.length][maps[0].length];
        int[][] shortestLoad = new int[maps.length][maps[0].length];
        for(int i = 0; i < shortestLoad.length; i++){
            for (int j = 0; j < shortestLoad[i].length; j++)
                shortestLoad[i][j] = -1;
        }
        Queue<int[]> queue = new LinkedList<>();

        int[] dx = {-1,0,1,0};
        int[] dy = {0,1,0,-1};
        queue.add(new int[]{0,0});
        checked[0][0] = true;
        shortestLoad[0][0] = 1;

        while (!queue.isEmpty()){
            int[] position = queue.remove();
            for(int i = 0; i < 4; i ++){
                int x = position[0] + dx[i];
                int y = position[1] + dy[i];
                if(isOk(x,maps.length) && isOk(y,maps[0].length) && !checked[x][y] && maps[x][y] != 0){
                    queue.add(new int[]{x,y});
                    checked[x][y] = true;
                    shortestLoad[x][y] = shortestLoad[position[0]][position[1]] + 1;
                }
            }
        }

        return shortestLoad[maps.length-1][maps[0].length-1];
    }

    private boolean isOk(int position, int maxLength){
        return  position >= 0 && position < maxLength;
    }
}

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)