게임 맵 최단거리

전형적인 DFS/BFS + 구현 문제

주의할점
maps의 가로 x 세로의 크기가 같지 않고 다를 수 도 있다는 점이다.
그래서 n,m을 재정의해서 풀어주었다.(처음 풀때는 가로 x 세로가 같은줄 알았다..) 문제를 잘 읽어보자

구현문제에서 제일 잘 나오는 4방향
북,동,서,남을 배열을 통해 정의해주고,
BFS,DFS에서 필수인 map과 크기가 같은 visitied 배열을 정의해주었다.

최단거리이므로 BFS를 활용했다.
BFS 로직에서 주의해야 할 점은 다음으로 이동할 부분이 맵을 넘어가는 경우 continue처리를 해주고,
다음으로 이동할 부분이 방문을 했는지, 이동 할 수 있는 파트인지 확인하고 이동해야한다.
visited배열에 이동횟수를 입력함으로써, 최종적으로 마지막 칸의 visited배열을 정답을 출력해주었다.

import java.util.*;

class Solution {
    public static int[] dy = new int[]{-1,0,1,0};
    public static int[] dx = new int[]{0,1,0,-1};

    // 방문 여부
    public static int[][] visited;
    public static int n;
    public static int m;

    public int solution(int[][] maps) {
        int answer = -1;

        n = maps.length;
        m = maps[0].length;

        visited = new int[n+1][m+1];

        for (int i = 0; i < visited.length; i++) { // 방문 초기화
            Arrays.fill(visited[i],0);
        }

        bfs(0,0, maps); // 0,0 부터 시작

        if(visited[n-1][m-1] > 0){
            answer = visited[n-1][m-1];
        }

        return answer;
    }

    // 최단거리 - BFS
    public void bfs(int y, int x, int[][] maps){
        visited[y][x] = 1;

        Node node = new Node(y,x);
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);

        while(!queue.isEmpty()){

            Node current = queue.poll();

            int cur_y = current.y;
            int cur_x = current.x;

            for (int i = 0; i < 4; i++) {
                int nx = cur_x + dx[i];
                int ny = cur_y + dy[i];

                if(nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                if(visited[ny][nx] == 0 && maps[ny][nx] == 1){ // 방문하지 않았고, 갈 수 있는 길인경우
                    visited[ny][nx] = visited[cur_y][cur_x] + 1; // 이전 방문한 값 + 1
                    queue.add(new Node(ny,nx));
                }
            }
        }
    }

    class Node {
        int x;
        int y;

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