[Programmers] 게임 맵 최단거리

// 1 <= n, m <= 100
// n과 m이 모두 1인경우는 주어지지 않는다.
// bfs를 이용해 최단거리 찾기

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

class Solution {
    static class Node{
        int length;
        int y;
        int x;
        Node(int y, int x, int length){
            this.y = y;
            this.x = x;
            this.length = length;
        }
    }
    static int[] dirX = {0, 1, 0, -1};
    static int[] dirY = {-1, 0, 1, 0};
    static int n,m;
    
    public int solution(int[][] maps) {
        int answer = -1;
        Queue<Node> q = new LinkedList<>();
        if(maps[0][0] == 1){
             q.add(new Node(0, 0, 1));   
        }
        n = maps.length;
        m = maps[0].length;
        while(!q.isEmpty()){
            Node node = q.poll();
            for(int i = 0; i < 4; i++){
                int y = node.y + dirY[i];
                int x = node.x + dirX[i];
                if(isGo(y, x, maps)){
                    if(y+1 == n && x+1 == m){
                        System.out.println(n + " " + m);
                        answer = node.length+1;
                        q.clear();
                    }
                    maps[y][x] = 0;
                    q.add(new Node(y, x, node.length+1));
                }
            }
        }
        return answer;
    }
    
    public boolean isGo(int y, int x, int[][] map){
        if(y < 0 || y >= n || x < 0 || x >= m || map[y][x] == 0){
            return false;
        }
        return true;
    }
}

BFS 기본문제다.