프로그래머스 깊이/너비 우선 탐색(DFS/BFS) LV2 - 게임 맵 최단거리

https://school.programmers.co.kr/learn/courses/30/lessons/1844?language=java

프로그래머스

맵이 주어졌을 때 (0,0)에서 (n,m)까지의 최단거리를 구하는 문제이다.

x,y,depth를 저장하는 클래스를 만들고 BFS를 이용해 탐색했다.

import java.util.*;
class Solution {
   int[] dx = {0,1,-1,0};
   int[] dy = {1,0,0,-1};
   public int solution(int[][] maps) {
        boolean[][] visited = new boolean[maps.length][maps[0].length];
        Queue<Lca> q = new LinkedList<>();
        q.offer(new Lca(0,0,1));
        int ans = -1;
        while(!q.isEmpty()){
            Lca temp = q.poll();
            int i = temp.x;
            int j = temp.y;
            int depth = temp.depth;
            if(i==maps.length-1&&j==maps[0].length-1){
                ans = depth;
            }
            if(visited[i][j]) continue;
            visited[i][j] = true;
            for (int k = 0; k < 4; k++) {
                if(check(i+dx[k],j+dy[k],visited,maps)){
                    q.offer(new Lca(i+dx[k],j+dy[k],depth+1));
                }
            }
        }
        return ans;
    }
    
    boolean check(int i, int j, boolean[][] visited, int[][] map){
        if(i<0||i>=map.length) return false;
        if(j<0||j>=map[0].length) return false;
        if(visited[i][j]) return false;
        if(map[i][j]==0) return false;
        return true;
    }
    
}

class Lca{
    int x;
    int y;
    int depth;
    Lca(int x, int y, int depth){
        this.x=x;
        this.y=y;
        this.depth = depth;
    }
}