[프로그래머스]게임 맵 최단거리 - BFS

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

프로그래머스

대표적인 BFS 문제입니다.

 

 

코드입니다.

import java.util.*;
class Solution {
    int[][] Maps;
    boolean[][] Visited;
    int answer = -1;
    public int solution(int[][] maps) {
        Maps = maps;
        BFS();
        return answer;
    }
    
    void BFS(){
        int[] dx = {-1,1,0,0};
        int[] dy = {0,0,-1,1};
        Queue<Node> q = new LinkedList<Node>();
        q.offer(new Node(0,0,1));
        Visited = new boolean[Maps.length][Maps[0].length];
        Visited[0][0] = true;
        while(!q.isEmpty()){
            Node temp = q.poll();
            if(temp.row == Maps.length-1 && temp.col == Maps[0].length -1 ){
                answer = temp.cnt;
                return ;
            }
            
            int cnt = temp.cnt;
            for(int dir=0;dir<4;dir++){
                int nrow = temp.row + dx[dir];
                int ncol = temp.col + dy[dir];
                if(nrow < 0 || nrow >= Maps.length || ncol < 0 || ncol >= Maps[0].length) continue;
                if(Maps[nrow][ncol] == 0 || Visited[nrow][ncol] == true) continue;        
                q.offer(new Node(nrow, ncol, temp.cnt + 1));
                Visited[nrow][ncol] = true;
            }
        }
        
    }
    class Node{
        int row;
        int col;
        int cnt;
        Node(int row, int col, int cnt){
            this.row = row;
            this.col = col;
            this.cnt = cnt;
        }
    }
}