프로그래머스 자바 :: 게임 맵 최단거리 (BFS)

 

 

 

 

import java.util.*;

class Solution {
    
    public static int n,m; 
    public static int answer = -1;
    
    public static int dx[] = {-1,1,0,0};
    public static int dy[] = {0,0,-1,1};
    public static boolean visited[][];
    
    public int solution(int[][] maps) {
        n = maps.length; // 행
        m = maps[0].length; // 열
        
        visited = new boolean[n][m]; // 방문배열여부 모두 false로 초기화

        return bfs(0, 0, maps);
    }
    
    int bfs(int x, int y, int[][] maps){
        Queue<int[]> q = new LinkedList<>(); // 큐!
        
        q.add(new int[]{x, y, 1}); // 1은 count 의미 (이동거리)
        visited[0][0] = true; // 시작점 방문 표시
        
        while(!q.isEmpty()){
            int temp[] = q.poll(); // 큐에서 꺼냄!
            x = temp[0];
            y = temp[1];
            int count = temp[2]; // 현재 위치까지 이동 거리
            
            // 도착점에 도달하면 답을 업데이트하고 종료
            if (x == n - 1 && y == m - 1) {
                answer = count;
                break;
            }
            
            for (int i = 0; i < 4; i++) { // 4인 이유 (방향 4개 상하좌우)
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                // 이동한 것이 맵을 벗어나면 무시
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                
                // 벽(0)이여도 무시
                if (maps[nx][ny] == 0) continue;
                
                // 방문하지 않은 길(1)일 경우
                if (!visited[nx][ny] && maps[nx][ny] == 1){
                    visited[nx][ny] = true; // 방문 표시
                    q.add(new int[]{nx, ny, count + 1}); // 큐에 추가하고 이동거리 +1
                }
            }
        }
        
        return answer;
        
    }
}