BJ1600 말이 되고픈 원숭이
https://www.acmicpc.net/problem/1600
BFS를 사용해 구현하는 문제이다.
하지만 점프 횟수라는 조건 때문에 방문처리를 할 때, 점프 횟수에 따라 각각의 맵에 따로 처리를 해주어야 한다.
boolean visit 배열을 3차원으로 만들어 해결해주었다.
package day0330;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class WannabeMonkey {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringTokenizer st;
static int jump, W, H;
static int[][] map;
static boolean[][][] visit;
static int[] dx = { 1, -1, 0, 0 };
static int[] dy = { 0, 0, 1, -1 };
static int[] hx = { -2, -2, 2, 2, 1, -1, 1, -1 };
static int[] hy = { 1, -1, 1, -1, 2, 2, -2, -2 };
static class Monkey {
int x;
int y;
int cnt;
int k;
Monkey(int x, int y, int cnt, int k) {
this.x = x;
this.y = y;
this.cnt = cnt;
this.k = k;
}
}
private static void bfs() throws IOException {
Queue<Monkey> q = new LinkedList<Monkey>();
q.add(new Monkey(0, 0, 0, jump));
while (!q.isEmpty()) {
Monkey curMonkey = q.poll();
int monkeyX = curMonkey.x;
int monkeyY = curMonkey.y;
int cnt = curMonkey.cnt;
int monkeyJump = curMonkey.k;
if (monkeyX == W - 1 && monkeyY == H - 1) {
bw.append(cnt + "");
return;
}
if (monkeyX >= W || monkeyY >= H || monkeyX < 0 || monkeyY < 0)
continue;
if (map[monkeyY][monkeyX] == 1)
continue;
if (visit[monkeyY][monkeyX][monkeyJump])
continue;
visit[monkeyY][monkeyX][monkeyJump] = true;
for (int i = 0; i < 4; i++) {
int nextX = monkeyX + dx[i];
int nextY = monkeyY + dy[i];
q.add(new Monkey(nextX, nextY, cnt + 1, monkeyJump));
}
if (monkeyJump != 0) {
for (int i = 0; i < 8; i++) {
int nextX = monkeyX + hx[i];
int nextY = monkeyY + hy[i];
q.add(new Monkey(nextX, nextY, cnt + 1, monkeyJump - 1));
}
}
}
bw.append("-1");
return;
}
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine(), " ");
jump = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine(), " ");
W = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
map = new int[H][W];
visit = new boolean[H][W][31];
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());
}
}
visit[0][0][0] = true;
bfs();
bw.flush();
}
}
Author And Source
이 문제에 관하여(BJ1600 말이 되고픈 원숭이), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mraz0210/BJ1600-말이-되고픈-원숭이저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)