[프로그래머스/Java] 게임 맵 최단거리 (BFS)

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

프로그래머스

 

★ Queue는 q.add() 대기열에 넣는 순간 visited = true 방문체크 해주기!!!!

 

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

class Node{
    int x, y, cost;
    
    Node(int x, int y, int cost){
        this.x = x;
        this.y = y;
        this.cost = cost;
    }
}

class Solution {
    Queue<Node> q = new LinkedList<>();
    boolean[][] visited;
    int[] dx = {-1, 1, 0, 0}; //상하좌우
    int[] dy = {0, 0, -1, 1};
    
    public int solution(int[][] maps) { // 0:벽 1:길
        int answer = 0;
        int n = maps.length, m = maps[0].length;
        
        visited = new boolean[n+1][m+1];
                
        q.add(new Node(1,1,1));
        visited[1][1] = true;
        
        return bfs(maps, n, m);
    }
    
    private int bfs(int[][] maps, int n, int m){
        while(!q.isEmpty()){
            Node current = q.poll();
            
            
            if(current.x == n && current.y == m){
                return current.cost;
            }
            
            for(int i=0; i<4; i++){
                int x = current.x + dx[i];
                int y = current.y + dy[i];
                
                if(x>=1 && x<=n && y>=1 && y<=m && maps[x-1][y-1]==1 && !visited[x][y]){
                    Node item = new Node(x,y,current.cost+1);
                    q.add(item);
                    visited[x][y]=true;
                }
            }
        }
        return -1;
    }
}