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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/1844?language=java

(0,0)에 위치한 캐릭터가 (4,4)에 위치한 상대팀 진영에 도착하기 위한 최단거리를 반환하는 문제이다.

캐릭터는 동, 서, 남, 북 방향으로 한칸씩 움직일 수 있으며 이때, 검은색 부분은 캐릭터가 이동할 수 없는 곳이다.

상대방 진영에 도달할 수 없으면 -1을 반환한다.

제한사항

maps는 n*m이며, 각각 1 이상 100 이하이다. (1 = n = m은 주어지지 않음)

maps의 각 요소는 0과 1이며, 0은 이동할 수 없는 부분이다.

캐릭터는 (0,0)이며, 상대방 진영은 (m-1, n-1)이다.

 

풀이

이 문제는 DFS 혹은 BFS의 기본적인 형태의 문제이다.

아래 혹은 오른쪽을 우선으로 탐색하도록 BFS를 구성하여 풀었다.

 

코드

public class Solution {
    public int[][] move = {
            {1,0,-1,0},
            {0,1,0,-1}
    };

    class Space {
        int x;
        int y;
        int cost;
        Space(int x, int y, int cost) {
            this.x = x;
            this.y = y;
            this.cost = cost;
        }
    }
    public int solution(int[][] maps) {
        boolean[][] visitedMap = new boolean[maps.length][maps[0].length];
        Queue<Space> queue = new LinkedList<>();
        Space space = new Space(0,0,1);
        queue.add(space);
        while(!queue.isEmpty() && !isFinish(maps, space)) {
            space = queue.poll();
            for(int i=0; i<4; i++) {
                Space nextSpace = new Space(space.x + move[0][i], space.y + move[1][i], space.cost + 1);
                if(isMovable(maps, visitedMap, nextSpace)) queue.add(nextSpace);
            }
        }
        if(queue.isEmpty() && !isFinish(maps, space)) return -1;
        return space.cost;
    }

    public boolean isMovable(int[][] maps, boolean[][] visited, Space space) {
        try { int temp = maps[space.y][space.x]; } catch (ArrayIndexOutOfBoundsException e) { return false; }
        if(maps[space.y][space.x]==0) return false;
        if(visited[space.y][space.x]) return false;
        visited[space.y][space.x] = true;
        return true;
    }

    public boolean isFinish(int[][] maps, Space space) {
        if(maps.length - 1 == space.y && maps[0].length - 1 == space.x) return true;
        return false;
    }
}