📌 풀이 과정
이 문제의 핵심은 3차원 방문 배열을 사용하는 것이다.
그리고 BFS를 활용할 때 좌표뿐만 아니라 현재 상태를 모두 포함해서 관리해야 한다.
💡 BFS에서 상태를 관리하는 방법
보통 BFS는 2차원 좌표 (x, y)만을 다룰 때 자주 사용한다. 하지만 이 문제에서처럼 좌표 외에도 말 찬스를 사용한 횟수(chance)와 같은 다른 상태를 포함해야 하는 경우도 있다. 이때 좌표와 chance를 하나의 상태로 묶어서 BFS 탐색을 진행해야 한다.
즉, 하나의 상태(state)가 (x, y, chance)로 표현된다.
이 상태에서 chance는 말처럼 이동하는 기회를 사용한 횟수를 나타내며, 같은 좌표 (x, y)라 하더라도 말 찬스를 얼마나 사용했는지에 따라 서로 다른 상태로 간주된다.
따라서 이 문제는 좌표와 말 찬스를 사용한 횟수를 동시에 관리해야 하므로
방문 체크도 좌표만이 아닌, 말 찬스를 사용한 횟수를 포함해야 한다.
🧐 구체적인 예
예를 들어, 같은 좌표 (3, 4)에 도착했다고 하더라도
- 말 찬스를 2회 사용한 상태와
- 말 찬스를 1회 사용한 상태는 서로 다른 상태 라고 본다.
따라서 이를 방문 체크할 때는, 좌표뿐 아니라 말 찬스를 사용한 횟수를 포함한 상태 (x, y, chance)로 관리해야 한다. 이걸 관리하기 위해 visited[x][y][chance]라는 3차원 배열을 사용한다.
🧐 예시 코드 설명
boolean[][][] visited = new boolean[H][W][K + 1];visited 배열은 좌표 (x, y)에 말 찬스를 chance번 사용한 상태로 도착한 적이 있는지를 기록하는 3차원 배열이다.
visited[x][y][chance] == true는
"좌표 (x, y)에 말 찬스를 chance번 사용한 상태로 도착한 적이 있다”는 의미이다.
이를 통해 같은 좌표에 도착했어도, 말 찬스를 몇 번 사용했는지에 따라 다른 경로를 추적할 수 있다.
💡 한 상태에 대해 BFS 탐색하는 방법
BFS를 진행할 때 상태 (x, y, chance)를 큐에 넣고 처리한다. 이동할 때는 일반 이동과 말처럼 이동할 수 있는 두 가지 경우가 있다.
-
일반 이동
- 좌표만 이동하며 말 찬스를 사용하지 않는 경우.
- 이때는
chance값이 변하지 않는다.
-
말처럼 이동
- 말처럼 이동할 기회를 사용해 좌표를 이동하는 경우.
- 이때는 chance 값을 1 증가시킵니다.
이 두 가지 경우 모두 새로운 상태 (nx, ny, chance)나 (nx, ny, chance + 1)를 큐에 넣고, 그 상태에 대해 방문 체크를 해야 한다.
✨ 제출 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int K, W, H;
static int[] dx = {-1, 1, 0, 0}; // 상하좌우로 이동하는 방향
static int[] dy = {0, 0, -1, 1};
static int[] hx = {-1, -2, -2, -1, 1, 2, 2, 1}; // 말처럼 이동하는 방향
static int[] hy = {-2, -1, 1, 2, 2, 1, -1, -2};
static int[][] world;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
K = Integer.parseInt(br.readLine()); // 말처럼 이동할 수 있는 최대 횟수
StringTokenizer st = new StringTokenizer(br.readLine());
W = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
world = new int[H][W]; // 세로(H) x 가로(W)
for (int i = 0; i < H; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < W; j++) {
world[i][j] = Integer.parseInt(st.nextToken());
}
}
System.out.println(bfs());
}
static int bfs() {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{0, 0, 0, 0}); // 시작점 (x, y, 사용한 말 찬스 수, 이동 횟수)
boolean[][][] check = new boolean[H][W][K + 1]; // 세로(H) x 가로(W) x 말 찬스
while (!q.isEmpty()) {
int[] cur = q.poll();
int x = cur[0];
int y = cur[1];
int chance = cur[2];
int move = cur[3];
if (x == H - 1 && y == W - 1) return move; // 목적지 도착
int nx, ny;
// 원숭이 4가지 방향 탐색 (상하좌우)
for (int i = 0; i < 4; i++) {
nx = x + dx[i];
ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= H || ny >= W || world[nx][ny] == 1) continue;
if (check[nx][ny][chance]) continue; // 이미 방문한 상태인지 확인
check[nx][ny][chance] = true;
q.offer(new int[]{nx, ny, chance, move + 1});
}
// 기회가 남아있다면, 말 8가지 방향 탐색
if (chance < K) {
for (int i = 0; i < 8; i++) {
nx = x + hx[i];
ny = y + hy[i];
if (nx < 0 || ny < 0 || nx >= H || ny >= W || world[nx][ny] == 1) continue;
if (check[nx][ny][chance + 1]) continue; // 말처럼 이동한 찬스를 사용한 적이 있는지 확인
check[nx][ny][chance + 1] = true;
q.offer(new int[]{nx, ny, chance + 1, move + 1});
}
}
}
return -1;
}
}