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

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

프로그래머스

 

BFS로 풀었다.

 

import java.util.*;

class Solution {
    
    public int[][] visited;
    public int[] dy = {-1,0,1,0};
    public int[] dx = {0,1,0,-1};
    public int n;
    public int m;
    
    public int solution(int[][] maps) {
        int answer = 0;
        n = maps.length;
        m = maps[0].length;
        
        visited = new int[n][m];
        
        bfs(visited, maps);
        
        answer = visited[n-1][m-1] == 0 ? -1 : visited[n-1][m-1];
        
        
        
        return answer;
    }
    
    public void bfs(int[][] visited, int[][] maps) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(0,0));
        visited[0][0] = 1;
        
        while(!queue.isEmpty()){
            Node cur = queue.poll();
            for(int i = 0; i < 4; i++){
                int ny = cur.y + dy[i];
                int nx = cur.x + dx[i];
                
                if(nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                if(maps[ny][nx] == 1 && visited[ny][nx] == 0) {
                    visited[ny][nx] = visited[cur.y][cur.x] + 1;
                    queue.add(new Node(ny, nx));
                }
            }
        }
    }
    
    public class Node {
        int y;
        int x;
        
        public Node(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
    
}