[알고리즘] 말이 되고픈 원숭이
2024. 2. 28. 14:42ㆍ알고리즘 풀이/Java
https://www.acmicpc.net/problem/1600
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main2 {
static int[][] map;
static int[][][] dp;
static int[] dr;
static int[] dc;
static int W;
static int H;
static int K;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
K = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
W = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
map = new int[W][H];
for (int i = 0; i < H; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < W; j++) {
map[j][i] = Integer.parseInt(st.nextToken());
if (map[j][i] == 1) {
map[j][i] = -1;
} else {
map[j][i] = Integer.MAX_VALUE;
}
}
}
dr = new int[] {-1, 1, 0, 0, 1, 1, 2, 2, -1, -1, -2, -2};
dc = new int[] {0, 0, -1, 1, 2, -2, 1, -1, 2, -2, 1, -1};
int result = bfs(new int[] {0, 0, 0, 0});
System.out.println(result);
}
private static int bfs(int[] start) {
Deque<int[]> deque = new ArrayDeque<>();
deque.add(start);
while (!deque.isEmpty()) {
int[] cur = deque.poll();
int r = cur[0];
int c = cur[1];
int jump = cur[2];
int time = cur[3];
if (r == W-1 && c == H-1) {
return time;
}
for (int i = 0; i < 12; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
if (0 <= nr && nr < W && 0 <= nc && nc < H && map[nr][nc] != -1) {
if (i >= 4) {
if (jump >= K) {
continue;
}
if (jump + 1 < map[nr][nc]) {
map[nr][nc] = jump + 1;
deque.add(new int[] {nr, nc, jump+1, time+1});
}
} else {
if (jump < map[nr][nc]) {
map[nr][nc] = jump;
deque.add(new int[] {nr, nc, jump, time+1});
}
}
}
}
}
return -1;
}
}
- 3차원 DP 배열로도 풀 수 있고(i, j, jump 각각을 차원으로) map 안에서 visited 역할로 갱신해주며 풀 수도 있다.
'알고리즘 풀이 > Java' 카테고리의 다른 글
[알고리즘] 프로세서 연결하기 (0) | 2024.02.29 |
---|---|
[알고리즘] 디버깅 꿀팁 (0) | 2024.02.29 |
[알고리즘] 파이프 옮기기 1 (1) | 2024.02.28 |
[알고리즘][X] 외판원 순회 2 (0) | 2024.02.28 |
[알고리즘] 1로 만들기 (0) | 2024.02.27 |