OJ
[BOJ] 1600 말이 되고픈 원숭이 (JAVA)
P3PP4
2022. 12. 13. 22:08
https://www.acmicpc.net/problem/1600
1600번: 말이 되고픈 원숭이
첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있
www.acmicpc.net
말처럼 행동할 수 있는 횟수를 가지고 다니는 것이 핵심입니다.
visited 배열은 3차원 배열이고, [말처럼 행동할 수 있는 횟수][행][열]로 선언했습니다.
Monkey 객체의 horse 변수가 말처럼 행동할 수 있는 횟수를 저장합니다.
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 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int H, W, K, time;
static int[][] arr;
static boolean[][][] visited;
// 기본 4방 탐색에서 쓰임
static int[] dr = { -1, 0, 1, 0 };
static int[] dc = { 0, 1, 0, -1 };
// 말처럼 움직일 때 쓰임
static int[] hdr = { -1, -2, -2, -1, 1, 2, 2, 1 };
static int[] hdc = { -2, -1, 1, 2, 2, 1, -1, -2 };
public static void main(String[] args) throws IOException {
K = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine(), " ");
W = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
arr = new int[H][W];
visited = new boolean[K + 1][H][W];
for (int i = 0; i < H; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < W; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
} // end of input
Queue<Monkey> q = new LinkedList<Monkey>();
q.offer(new Monkey(0, 0, K));
visited[K][0][0] = true;
while(!q.isEmpty()) {
int size = q.size();
while(size-- > 0) {
Monkey now = q.poll();
// 목적지 도달
if(now.row == H - 1 && now.col == W - 1) {
System.out.println(time);
return;
}
for (int i = 0; i < 4; i++) {
int nr = now.row + dr[i];
int nc = now.col + dc[i];
if(0 <= nr && nr < H && 0 <= nc && nc < W && !visited[now.horse][nr][nc] && arr[nr][nc] != 1) {
q.offer(new Monkey(nr, nc, now.horse));
visited[now.horse][nr][nc] = true;
}
}
// 아직 말처럼 움직일 수 있다면
if (0 < now.horse) {
for (int i = 0; i < 8; i++) {
int nr = now.row + hdr[i];
int nc = now.col + hdc[i];
if (0 <= nr && nr < H && 0 <= nc && nc < W && !visited[now.horse - 1][nr][nc] && arr[nr][nc] != 1) {
q.offer(new Monkey(nr, nc, now.horse - 1));
visited[now.horse - 1][nr][nc] = true;
}
}
}
}
time++;
}
System.out.println(-1);
}
static class Monkey {
int row, col, horse;
public Monkey(int row, int col, int horse) {
this.row = row;
this.col = col;
this.horse = horse;
}
}
}