[백준 1600] 말이 되고픈 원숭이 (JAVA)
문제
풀이
BFS로 해결할 수 있습니다.
말로 움직이는 방법까지 카운트할 수 있는 3차원 형태의 배열로 방문처리([말카운트][H][W])를 하면 쉽게 해결할 수 있습니다.
코드
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, H, W;
static boolean[][][] visited;
static int[][] map;
static int[][] monkey = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
static int[][] horse = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
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());
visited = new boolean[K+1][H][W];
map = new int[H][W];
for (int i = 0; i < H; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < W; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
System.out.println(bfs());
br.close();
}
public static int bfs() {
Queue<Loc> q = new LinkedList<>();
q.add(new Loc(0, 0, 0));
visited[0][0][0] = true;
int step = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int s = 0; s < size; s++) {
Loc loc = q.poll();
if (loc.x == H - 1 && loc.y == W - 1) return step;
// horse
if (loc.cnt < K) {
for (int d = 0; d < 8; d++) {
int dx = loc.x + horse[d][0];
int dy = loc.y + horse[d][1];
int cnt = loc.cnt + 1;
if (check(dx, dy, cnt)) {
q.add(new Loc(dx, dy, cnt));
visited[cnt][dx][dy] = true;
}
}
}
// monkey
for (int d = 0; d < 4; d++) {
int dx = loc.x + monkey[d][0];
int dy = loc.y + monkey[d][1];
if (check(dx, dy, loc.cnt)) {
q.add(new Loc(dx, dy, loc.cnt));
visited[loc.cnt][dx][dy] = true;
}
}
}
step++;
}
return -1;
}
public static boolean check(int dx, int dy, int cnt) {
return dx >= 0 && dx < H && dy >= 0 && dy < W && !visited[cnt][dx][dy] && map[dx][dy] == 0;
}
public static class Loc {
int x, y, cnt;
public Loc(int x, int y, int cnt) {
this.x = x;
this.y = y;
this.cnt = cnt;
}
}
}
Author And Source
이 문제에 관하여([백준 1600] 말이 되고픈 원숭이 (JAVA)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@solser12/백준-1600-말이-되고픈-원숭이-JAVA저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)