[프로그래머스 Level 2] 게임 맵 최단거리 [자바]

 

 

---

※. BFS로 풀어야함

 

※. 0 이 벽이 있는 자리

 

※. (1,1) 시작위치도 지나야 하는 칸에 포함된다.

 

---

import java.util.*;

class Position {
    int x,y;
    Position(int x, int y) {
        this.x = x;
        this.y = y;
    }
    
    boolean isValid(int w, int h) {
        if(x < 0 || x >= h) return false;
        if(y < 0 || y >= w) return false;
        return true;
    }
}
class Solution {
    public int solution(int[][] maps) {
        int answer = -1;
        int height = maps.length;
        int width = maps[0].length;
        
        Queue<Position> que = new LinkedList<>();
        int[][] visited = new int[height][width];
        
        int[][] moving = {{0,-1},{0,1},{-1,0},{1,0}};
        
        que.add(new Position(0,0));
        visited[0][0] = 1;
        while(!que.isEmpty()) {
            Position c = que.poll();         
            
            for(int i = 0; i < 4; i++) {
                Position moved = new Position(c.x + moving[i][0], c.y + moving[i][1]);
                
                if(!moved.isValid(width, height)) continue;
                if(maps[moved.x][moved.y] == 0) continue;
                if(visited[moved.x][moved.y] == 0 || visited[moved.x][moved.y] > visited[c.x][c.y] + 1) {
                    visited[moved.x][moved.y] = visited[c.x][c.y] + 1;
                    que.add(moved);
                }
            }
        }
        answer = visited[height-1][width-1];
        if(answer == 0) answer = -1;
        return answer;
    }
}