[프로그래머스] 보물 지도 🗺️ (Java)

문제 링크

✅ 문제 파악

당신은 신비한 보물지도를 들고, 시작점 (1, 1)에서 도착점 (n, m)으로 이동하려고 한다.
지도는 n x m 크기의 격자 형태이며, 일부 칸에는 함정이 있어 해당 칸으로는 이동할 수 없다.
당신에게는 단 한 번 사용할 수 있는 신비로운 신발이 주어진다.
이 신발을 사용하면 상하좌우 중 한 방향으로 2칸을 점프할 수 있다.
그 외에는 일반적인 상하좌우 1칸 이동만 가능하다.

조건 요약

• 1칸 이동: 상하좌우 (시간 +1)
• 2칸 점프: 상하좌우 (시간 +1, 단 1회만 사용 가능)
• 함정 칸은 이동 및 착지 불가
• (1, 1) → (n, m)까지 최소 시간을 구하라.
  도달할 수 없다면 -1을 반환하라.

🎯 접근 방법

1. 입력 기반 상태 초기화

   boolean[][] trap = new boolean[n + 1][m + 1];
   for (int[] h : hole) {
       trap[h[0]][h[1]] = true;
   }

   • 함정 좌표를 표시하기 위해 trap 배열을 선언함.
   • 지도는 1부터 시작하므로 인덱스를 n+1, m+1로 확보하고,
   • hole 배열을 순회하며 trap[x][y] = true로 설정해 해당 칸을 이동 불가로 처리.

2. 방문 여부 및 시작 상태 설정

   boolean[][][] visited = new boolean[n + 1][m + 1][2];
   ArrayDeque<int[]> queue = new ArrayDeque<>();
   queue.add(new int[]{1, 1, 0, 0});
   visited[1][1][0] = true;

   • visited[x][y][0/1]로 구성된 3차원 방문 배열을 사용해
     • [x][y][0]: 아직 점프를 쓰지 않고 방문한 상태
     • [x][y][1]: 점프를 한 번 사용하고 방문한 상태를 구분.
   • (1,1)에서 출발하므로 큐에 [1, 1, 0, 0] 삽입:
     • x=1, y=1, jumped=0(점프 안 씀), dist=0

3. 이동 방향 정의

   int[][] step1 = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
   int[][] step2 = {{-2, 0}, {2, 0}, {0, -2}, {0, 2}};

   • 일반적인 이동은 상하좌우 1칸씩 (step1)
   • 점프는 상하좌우로 2칸씩 (step2)

4. BFS 탐색 수행

   while (!queue.isEmpty()) {
       int[] curr = queue.poll();
       int x = curr[0], y = curr[1], jumped = curr[2], dist = curr[3];

   • 큐에서 현재 상태를 꺼내 탐색 시작
   • 현재 위치와 점프 사용 여부, 누적 거리 정보를 저장

5. 도착 지점 확인

   if (x == n && y == m) {
       return dist;
   }

   • 현재 좌표가 도착지 (n, m)이면 누적 거리 dist를 반환하고 종료

6. 상하좌우 1칸 이동 처리

   for (int i = 0; i < 4; i++) {
       int newX = x + step1[i][0];
       int newY = y + step1[i][1];
   
       if (newX >= 1 && newX <= n && newY >= 1 && newY <= m &&
           !trap[newX][newY] && !visited[newX][newY][jumped]) {
   
           visited[newX][newY][jumped] = true;
           queue.add(new int[]{newX, newY, jumped, dist + 1});
       }
   }

   • 상하좌우 1칸씩 이동을 시도
   • 이동한 위치가 범위 내이고, 함정이 아니며, 같은 점프 상태에서 방문하지 않았다면:
     • 해당 위치를 방문 처리하고,
     • jumped 상태를 유지한 채 큐에 추가

7. 점프 이동 (단, 한 번만 가능)

   if (jumped == 0) {
       for (int i = 0; i < 4; i++) {
           int newX = x + step2[i][0];
           int newY = y + step2[i][1];
   
           if (newX >= 1 && newX <= n && newY >= 1 && newY <= m &&
               !trap[newX][newY] && !visited[newX][newY][1]) {
   
               visited[newX][newY][1] = true;
               queue.add(new int[]{newX, newY, 1, dist + 1});
           }
       }
   }

   • 점프는 아직 사용하지 않은 경우(jumped == 0)에만 실행
   • 상하좌우 2칸 떨어진 위치로 점프 시도
   • 점프 후에는 jumped = 1 상태로 큐에 삽입하고 해당 위치 방문 처리

8. 종료 조건

   return -1;

   • 큐가 전부 소진될 때까지 도착지에 도달하지 못하면 -1 반환

✨ 전체 코드

import java.util.*;

class Solution {
    public int solution(int n, int m, int[][] hole) {
        // 함정 표시
        boolean[][] trap = new boolean[n + 1][m + 1];
        for (int[] h : hole) {
            trap[h[0]][h[1]] = true;
        }
        
        // 방문 여부 (0 -> 점프 안씀 / 1 -> 점프 씀)
        boolean[][][] visited = new boolean[n + 1][m + 1][2];
        
        ArrayDeque<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{1, 1, 0, 0}); // 시작 지점
        visited[1][1][0] = true;
        
        int[][] step1 = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int[][] step2 = {{-2, 0}, {2, 0}, {0, -2}, {0, 2}};
        
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int x = curr[0];
            int y = curr[1];
            int jumped = curr[2];
            int dist = curr[3];
            
            // 도착 지점 도달
            if (x == n && y == m) {
                return dist;
            }
            
            // 1칸 이동
            for (int i = 0; i < 4; i++) {
                int newX = x + step1[i][0];
                int newY = y + step1[i][1];
                
                if (newX >= 1 && newX <= n && newY >= 1 && newY <= m && !trap[newX][newY] && !visited[newX][newY][jumped]) {
                    visited[newX][newY][jumped] = true;
                    queue.add(new int[]{newX, newY, jumped, dist + 1});
                    
                }
            }
            
            // 2칸 이동
            if (jumped == 0) {
                for (int i = 0; i < 4; i++) {
                    int newX = x + step2[i][0];
                    int newY = y + step2[i][1];
                
                    if (newX >= 1 && newX <= n && newY >= 1 && newY <= m && !trap[newX][newY] && !visited[newX][newY][1]) {
                        visited[newX][newY][1] = true;
                        queue.add(new int[]{newX, newY, 1, dist + 1});
                    }
                }
            }
        }
        return -1;
    }
}