[Programmers] 게임 맵 최단거리

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

---

[BFS]

BFS의 가장 전형적인 문제. 최단거리를 구할 때 DFS를 이용하려할 수도 있는데, 이는 잘못된 것이다. DFS가 탐색하는 곳은 항상 최적해(최단거리)는 아니기 때문이다.

# Code </>

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

class Solution {

    static class Point{
        int y, x, move;

        public Point(int y, int x, int move) {
            this.y = y;
            this.x = x;
            this.move = move;
        }
    }

    static int[] Y = {-1, 1, 0, 0}, X = {0, 0, -1, 1};
    static int BFS(int[][] maps, int r, int c){

        boolean[][] visit = new boolean[r][c];
        Queue<Point> Q = new LinkedList<>();

        visit[0][0] = true;
        Q.add(new Point(0, 0, 1));

        while(!Q.isEmpty()){
            Point p = Q.poll();
            int y = p.y;
            int x = p.x;
            int m = p.move;

            if(y == r-1 && x == c-1)
                return m;

            for(int a=0; a<4; a++){
                int ny = y+Y[a];
                int nx = x+X[a];

                if(ny < 0 || nx < 0 || ny > r-1 || nx > c-1 || visit[ny][nx] || maps[ny][nx] == 0) continue;

                visit[ny][nx] = true;
                Q.add(new Point(ny, nx, m+1));
            }
        }

        return -1;
    }

    public int solution(int[][] maps) {

        int r = maps.length;
        int c = maps[0].length;

        return BFS(maps, r, c);
    }
}