Lv.2-[게임 맵 최단거리]

문제

문제링크

제한사항

코드

import java.util.*;
class Solution {
    static int[] mx = {0,1,0,-1};
    static int[] my = {1,0,-1,0};
    static boolean[][] visit;
    static int n,m;
    public static class Node{
        int x;
        int y;
        int dis;
        public Node(int x, int y , int dis){
            this.x = x;
            this.y = y;
            this.dis = dis;
        }
    }
    public static int BFS(int x, int y, int[][] maps){
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(x,y,1));
        visit[x][y] = true;
        
        while(!queue.isEmpty()){
            Node node = queue.poll();
            if(node.x == n-1 && node.y == m - 1){ // 제일 마지막 도착했을 경우
                return node.dis;
            }
            for(int i=0; i<4; i++){
                int px = node.x + mx[i];
                int py = node.y + my[i];
                if(px >= 0 && py >=0 && px<n && py<m){ // map 경계 안에 있을 경우
                    if(maps[px][py]==1 && !visit[px][py]){ // 1(흰색부분) 이면서 방문하지 않은 칸
                        visit[px][py] = true;
                        queue.offer(new Node(px,py,node.dis+1));
                    }
                }
            }
        }
        return -1;
    }
    public int solution(int[][] maps) {
        n = maps.length;
        m = maps[0].length;
        
        visit = new boolean[n][m];
        return BFS(0,0,maps);
    }
}

알고 넘어가기

이렇게 미로처럼 최단거리를 구할 때 BFS를 사용한다. DFS를 할 경우 풀리는 경우도 있지만 시간초과가 날 때가 있기때문에 BFS를 활용하자!!