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

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

프로그래머스

 

프로그머스 연습문제에 있는 DFS, BFS 문제입니다. BFS 로 해결이 가능하며 지정한 도착점에 도달하지 못하는 경우에는 -1로 출력하고, 그렇지 않으면 가장 빠르게 도착하는 count 를 출력하면 됩니다. BFS 알고리즘을 활용하면 가장 빠르게 도달하는 route 로 탐색할 수 있고, 최소 비용의 값을 리턴할 수 있습니다. DFS 와는 다르게 BFS 는 너비 우선 탐색을 수행하기 때문입니다.

 

예제 코드는 아래와 같습니다.

import java.util.*;

class Point {
    int y;
    int x;
    int count;

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

class Solution {
    public static int dy[] = {0,1,0,-1};
    public static int dx[] = {1,0,-1,0};
    public static int solution(int[][] maps) {
        int answer = -1;
        int maxY = maps.length;
        int maxX = maps[0].length;
        boolean visited[][] = new boolean[maxY][maxX];
        Queue<Point> bfs = new LinkedList<>();
        bfs.add(new Point(0,0,1));
        visited[0][0] = true;
        while(!bfs.isEmpty()) {
            Point p = bfs.poll();
            if (p.y == maxY - 1 && p.x == maxX - 1) {
                return p.count;
            }
            for (int i = 0; i < 4; i++) {
                int ny = p.y + dy[i];
                int nx = p.x + dx[i];
                if (check(maxY, maxX, ny, nx) && maps[ny][nx] == 1 && !visited[ny][nx]) {
                    bfs.add(new Point(ny,nx, p.count+1));
                    visited[ny][nx] = true;
                }
            }
        }
        return answer;
    }

    public static boolean check(int maxY, int maxX, int y, int x) {
        return y >= 0 && y < maxY && x >= 0 && x < maxX;
    }
}