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

코딩테스트 연습 - 게임 맵 최단거리 | 프로그래머스 (programmers.co.kr)

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

어떻게 생각하고 문제를 풀었는가?

그래프 탐색이므로 DFS 또는 BFS를 사용해야 겠다고 생각이 들었습니다.

DFS를 사용할 경우 모든 경로를 탐색한 후 거리들을 비교하여 최소값을 반환하여 해결할 수 있지만

BFS는 먼저 목적지에 도달한 경로가 최단 거리의 경로이므로 더 빠르게 결과를 얻을 수 있다고 생각했습니다.

 

코드

import java.util.Queue;
import java.util.LinkedList;
class Solution {
    final int[] px = {-1,0,1,0}, py = {0,-1,0,1};
    
    private class Tile{
        int x;
        int y;
        int meter;
        Tile(int x, int y, int meter){
            this.x = x;
            this.y = y;
            this.meter = meter;
        }
    }
    
    public int solution(int[][] maps) {
        int rows = maps.length;
        int columns = maps[0].length;
        boolean[][] visited = new boolean[rows][columns];
        
        Queue<Tile> queue = new LinkedList<>();
        queue.offer(new Tile(0,0,1));
        while(!queue.isEmpty()){
            Tile current = queue.poll();
            if(current.x == rows-1 && current.y == columns-1) return current.meter;
            
            for(int i=0; i<4; i++){
                int nx = current.x + px[i];
                int ny = current.y + py[i];
                if(nx>=0 && nx<rows && ny>=0 && ny<columns){
                    if(maps[nx][ny]==1 && !visited[nx][ny]){
                        visited[nx][ny] = true;
                        queue.offer(new Tile(nx,ny,current.meter+1));    
                    }
                }
            }
        }
        return -1;
    }
    
} 

BFS를 구현하기 위해 이동할 타일 정보를 Queue에 삽입하고, 이동가능한 타일이 없을 때까지 반복하도록 코드를 작성하였습니다.

목적지에 도달한 경우 이동한 거리를 즉시 반환함으로서 원하는 결과를 얻을 수 있고 Queue를 모두 순회할 때까지 목적지에 도착하지 못한 경우 갈 수 없음을 의미하므로 -1을 반환합니다.