[프로그래머스 Lv.2] 게임 맵 최단거리(Java)

문제 설명

게임 맵 최단거리 문제는 다음과 같습니다.

• 시작점에서 도착점까지 갈 수 있는 최단거리를 구합니다.
• 맵은 1과 0으로 이루어진 2차원 배열로 표현되며, 1은 이동할 수 있는 곳, 0은 이동할 수 없는 곳입니다.
• 시작점은 (1, 1)이고 도착점은 (n, m)입니다.
• 이동 방향은 상하좌우로 한 칸씩만 가능합니다.

---

풀이 방식

BFS를 사용하면 최단거리 탐색 문제를 효율적으로 해결할 수 있습니다.

BFS는 한 지점에서 갈 수 있는 모든 경우를 단계적으로 탐색하기 때문에

목적지에 도착했을 때의 거리가 최단거리임을 보장합니다.

---

코드 설명

import java.util.*;

class Solution {
	static int[] dx = {0, 0, -1, 1}; // 상하좌우
    static int[] dy = {1, -1, 0, 0}; // 상하좌우
    
    public int solution(int[][] maps) {
    	return BFS(maps);
    }
    
    private static int BFS(int[][] maps) {
    	// BFS 탐색용 큐
    	Queue<int[]> queue = new LinkedList<>();
        // 방문 여부 확인
        boolean[][] visited = new boolean[maps.length][maps[0].length];
        // 시작점 { x좌표, y좌표, 현재 거리 }
        int[] start = { 0, 0, 1 };
        
        queue.add(start);
        visited[0][0] = true; // 시작점 방문 처리
        
        while(!queue.isEmpty()) {
        	int[] arr = queue.poll();
            int x = arr[0];
            int y = arr[1];
            int cnt = arr[2];
            
            // 목적지에 도착한 경우
            if(x == maps.length-1 && y == maps[0].length-1)
            	return cnt; // 현재까지 이동한 거리 반환
            
            // 상하좌우 이동 탐색
            for(int i=0; i<4; i++) {
            	int nx = x + dx[i];
                int ny = y + dy[i];
                
                // 맵의 범위를 벗어난 경우 무시
                if(nx == maps.length || nx < 0 || ny == maps[0].length || ny < 0)
                	continue;
                    
                // 이미 방문했거나 이동할 수 없는 칸인 경우 무시
                if(visited[nx][ny] || maps[nx][ny] != 1)
                	continue;
                
                // 새로운 위치 방문 처리 및 큐에 추가
                visited[nx][ny] = true;
                int[] nextArr = { nx, ny, cnt+1 }; // 거리 + 1
                queue.add(nextArr);
            }
        }
        return -1; // 도착할 수 없는 경우
    }
}

---

코드 해석

1. BFS 준비

• queue를 생성하고, 시작점(0, 0)을 queue에 추가한다.
• visited 배열로 방문 여부를 기록하여 중복 방문을 방지한다.

2. BFS 탐색

• 큐에서 하나의 위치 정보를 꺼내 (x, y, 거리)를 가져온다.
• 현재 위치가 도착점(n - 1, m - 1)인지 확인하고 도착했다면 최단거리(cnt)를 반환한다.

3. 상하좌우 이동

• dx와 dy 배열을 이용해 상하좌우로 이동한다.
• 이동할 위치가 맵의 범위를 벗어나거나, 이미 방문했거나, 0인 경우는 무시한다.(continue)
• 이동 가능한 경우, 방문 처리 후 queue에 (nx, ny, 거리+1)를 추가한다.

4. 목적지에 도달하지 못한 경우

• 모든 탐색이 끝난 후에도 도착점에 도달하지 못해다면 -1을 반환한다.

---

왜 (1, 1) 대신 (0, 0)을 사용하는가?

2차원 배열의 첫번째 행과 첫번째 열은 (0, 0)에 위치한다.

따라서 문제에서 (1, 1) 위치를 가리키는 것은 배열에서 실제로 (0, 0) 인덱스에 해당한다.

마찬가지로 (n, m)은 배열의 마지막 위치(n - 1, m - 1)로 변환된다.

---

시간 복잡도

O(N * M)

모든 칸을 한 번씩 방문하므로 맵의 크기에 비례한다.

---