게임 맵 최단거리

이건 지금 내 레벨이 아니라 느끼고 풀이를 보고 그냥 완전탐색을 공부하기로 합의봤다ㅎ

일단 코드를 보자.

 

ㅇ 코드

class Solution {
    public int solution(int[][] maps) {
        int n = maps.length; //maps의 행 수
        int m = maps[0].length;	//maps의 열 수
        int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; // 동, 남, 서, 북으로의 이동

        Queue<int[]> queue = new LinkedList<>();//BFS를 위한 큐 초기화
        queue.offer(new int[]{0, 0, 1}); // 시작 지점 (0, 0)에 도착했으므로 거리는 1

        while (!queue.isEmpty()) {//큐가 비어있지 않을동안 계속해서 반복
            int[] current = queue.poll();//큐에서 현재위치 꺼내서 current에 저장
            //현재위치와 거리를 변수에 저장
            int x = current[0];
            int y = current[1];
            int distance = current[2];
			
            if (x == n - 1 && y == m - 1) { // 상대 팀 진영에 도착한 경우 거리반환
                return distance;
            }

            for (int[] dir : dirs) {//동,남,서,북 확인하면서 새로운 위치newX, newY계산
                int newX = x + dir[0];
                int newY = y + dir[1];
				//다음 위치가 게임 맵 안에있고, 그 위치에 벽이 없는경우에
                if (newX >= 0 && newX < n && newY >= 0 && newY < m && maps[newX][newY] == 1) {
                    maps[newX][newY] = 0; // 해당 칸을 방문했음을 표시
                    queue.offer(new int[]{newX, newY, distance + 1});//새로운위치를 큐에 저장하고 거리를 1증가
                }
            }
        }

        return -1; // 상대 팀 진영에 도착할 수 없는 경우
    
    }
}

솔직히 봐도 잘 모르겠긴 하다. 완전탐색에대해 자세히 블로깅해보고 다시 돌아와서 이 코드를 이해해보겠다.