[Programmers] 게임 맵 최단거리 (Java)

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

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

 

문제

 

N x M 배열이 입력값으로 주어진다. (1, 1) 지점에서 시작해서 (N, M) 지점에 도달했을 때의 최단 거리를 구하는 문제입니다. 단, (N, M) 지점에 도달하지 못했을 때는 -1을 반환해줍니다.

 

접근 아이디어

 

1. 최단거리를 구하는 문제에 필요한 BFS 알고리즘을 이용하였습니다.

2. 이전에 방문했는지를 체크하는 visit 배열을 사용하였습니다.

3. (1, 1) 지점을 시작으로 모든 방향에 대해 갈 수 있는 지점인지 (벽 또는 범위 내), 이미 방문하였는지를 체크해줍니다.

4. 결과값으로 (N, M) 에 지점에 도착했을 때의 지나간 거리를, 도착할 수 없다면 -1을 반환해 줍니다. 

 

조심해야할 점

 

1. 입력값은 N x M 행렬이 들어오므로 행과 열의 갯수가 다르다는점을 생각해야 한다.

2. (N, M) 지점에 도착하지 못하는 경우도 고려해야 한다.

 

- Java

import java.util.*;

class Solution {

    static int area = 1;
    static boolean[][] visit;
    static int[][] dirs = {{0, 1},{1, 0},{0, -1},{-1, 0}};

    public int solution(int[][] maps) {
        int col = maps.length;
        int row = maps[0].length;
        visit = new boolean[col][row];

        for(int i=0; i<col; i++) {
            for(int j=0; j<row; j++) {
                if(maps[i][j] == 1) area++;
            }
        }

        return bfs(maps);
    }

    private int bfs(int[][] maps) {
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(0, 0, 1));
        visit[0][0] = true;

        int result = -1;

        while(!queue.isEmpty()) {
            Point now = queue.poll();
            int x = now.x;
            int y = now.y;
            if(x == visit.length - 1 && y == visit[0].length - 1) {
                result = now.dir;
                break;
            }
            for(int i=0; i<4; i++) {
                int nextX = x + dirs[i][0];
                int nextY = y + dirs[i][1];

                if(!inRange(nextX, nextY)) continue; //범위 내에 있는지 확인
                if(maps[nextX][nextY] == 0) continue; //벽인지 확인
                if(visit[nextX][nextY]) continue; //이전에 방문했는지 확인

                queue.add(new Point(nextX, nextY, now.dir + 1));
                visit[nextX][nextY] = true;
                area--;
            }
        }

        return result;
    }

    private boolean inRange(int x, int y) {
        int col = visit.length;
        int row = visit[0].length;

        return x >= 0 && y >= 0 && x < col && y < row;
    }

    static class Point {
        int x;
        int y;
        int dir;
        Point(int x, int y, int dir) {
            this.x = x;
            this.y = y;
            this.dir = dir;
        }
    }
}