게임 맵 최단거리

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

프로그래머스

 

최단 거리를 구하는 문제이므로 bfs를 사용했다.

 

시작 지점도 지나가야하는 칸에 포함된다는 것에 유의..

 

import java.util.*;

class Solution {
    
    static final int[] dx = { 1, 0, -1, 0 };
    static final int[] dy = { 0, 1, 0, -1 };
    
    public int solution(int[][] maps) {
        
        boolean[][] visited = new boolean[maps.length][maps[0].length];
        
        Queue<Position> queue = new LinkedList();
        queue.add(new Position());
        
        while (!queue.isEmpty()) {
            
            Position p = queue.poll();
            
            if (p.x < 0 || p.y < 0 || p.x >= maps[0].length || p.y >= maps.length) continue;
            
            if (visited[p.y][p.x]) continue;
            
            if (maps[p.y][p.x] == 0) continue;
            
            if (p.x == maps[0].length - 1 && p.y == maps.length - 1) return p.moved;
            
            visited[p.y][p.x] = true;
            
            for (int i = 0; i < 4; i++) {
                Position next = p.move(i);
                queue.add(next);
            }
            
        }
        
        return -1;
    }
    
    static class Position {
        int x;
        int y;
        int moved = 1;
        Position move(int i) {
            Position vo = new Position();
            vo.x = x + dx[i];
            vo.y = y + dy[i];
            vo.moved = moved + 1;
            return vo;
        }
    }
    
}