Skip to main content

[Java] 1844 게임 맵 최단거리

1. 문제

게임 맵 최단거리

image.png

image.png

image.png

2. 접근 방법

  1. ​시작점 (0, 0)에서 BFS를 시작한다.
  2. 갈 수 있는 길(maps[r][c] == 1) 이동
  3. 방문할 때마다 현재까지의 칸수 기록
  4. 도착점 (n - 1, m - 1)에 도달하면 해당 칸에 기록된 값이 최단거리
  5. BFS 탐색이 끝났는데 도착점에 도달하지 못했다면 -1 반환

3. 정답 코드

BFS

import java.util.*;

class Solution {
    
    static class Point {
        int x,y;
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public int solution(int[][] maps) {
        int n = maps.length;
        int m = maps[0].length;
        
        // 방향 배열 (상, 하, 좌, 우)
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(0, 0));
        
        // BFS로 거리 누적하기 (여기서 시작점 1로 잡음)
        // maps 배열에 거리 값 직접 지정
        while (!queue.isEmpty()) {
            Point p = queue.poll();
            
            for (int i = 0; i < 4; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                
                // 맵 범위 확인
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                
                // 길이고 아직 방문하지 않은 경우
                if (maps[nx][ny] == 1) {
                    maps[nx][ny] = maps[p.x][p.y] + 1; // 거리 누적
                    queue.add(new Point(nx, ny));
                }
            }
        }
        
        return maps[n-1][m-1] == 1 ? -1 : maps[n-1][m-1];
    }
}

4방향 탐색

dx = {-1, 1, 0, 0}
dy = {0, 0, -1, 1}
  • x좌표 (행 번호) 기준 -1는 한칸 위, +1은 한 칸 아래
    • 위쪽으로 한 칸 (x - 1)
    • 아래쪽으로 한 칸 (x + 1)
  • y좌표 (열 번호) 기준 -1는 좌로 한 칸 이동, +1은 우로 한 칸 이동
    • 왼쪽으로 한 칸 (y - 1)
    • 오른쪽으로 한 칸 (y + 1)
  • for (int i = 0; i < 4; i++) 루프 돌면서 (x + dx[i], y + dy[i]) 계산하면 상하좌우 네 방향 전부 확인 가능

방문한 칸을 따로 배열에 저장 안 하고 maps 에 거리값 덮어쓴 이유

2가지 방법이 있다.

  1. 방문 여부 + 거리 저장을 maps에 덮어 쓰기 (이게 내가 한 방법)
    • maps[x][y] == 1 아직 방문하지 않은 길
    • maps[x][y] == maps[이전칸] + 1
      • 이렇게 해서 몇 번째 칸에 도달했는지 거리 기록
      • 이렇게 하면 visited[][] 안만들어도 됨
  2. maps는 그대로 두고 visited, dist배열 따로쓰기
    • boolean[][] visited → 방문여부 체크
    • int[][] dist → 해당 칸까지의 최단 거리 저장
      • 이렇게 하면 원본 맵 보존 가능
maps[nx][ny] = maps[x][y] + 1;

단순히 방문 체크 하는게 아니라 여기까지 오는데 몇 칸 걸렸는지 바로 저장 가능

맵 범위 확인

if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
  • BFS에서 상하좌우로 이동할 때 새로운 좌표 (nx, ny)를 만든다
  • 근데 만약에 (nx, ny)가 맵 밖으로 나가면 ArrayIndexOutOfBoundsException 에러가 나기 때문에 좌표가 맵 안에 있는지 확인하는 로직이다
    • nx < 0 → 위로 나가서 맵 밖 (행 음수)
    • ny < 0 → 왼쪽으로 나가서 맵 밖 (열 음수)
    • nx >= n → 아래로 나가서 맵 밖 (행이 전체 크기 n 이상)
    • ny >= m → 오른쪽으로 나가서 맵 밖 (열이 전체 크기 m이상)


Back to top