문제 URL : www.acmicpc.net/problem/1600
1600번: 말이 되고픈 원숭이
첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있
www.acmicpc.net
문제 접근법: k번만 체스판 나이트처럼 이동이 가능하고 그외는 좌우상하 1칸씩 이동해서 맨오른쪽 아래칸으로 갈수있는지 확인하면 됩니다. 최소이동겨로로 가기때문에 BFS를 이용하면 됩니다.
주의할점은 입력이 열,행 이렇게 받기때문에 행,열로 받지 않기를 주의하시길
이번엔 자바 코드를 올리겠습니다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
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;
public class Main {
static int n, m;
static int board[][];
static int dy[] = { -1, 0, 1, 0 };
static int dx[] = { 0, 1, 0, -1 };
static int hy[] = { -2, -2, -1, -1, 1, 1, 2, 2 };
static int hx[] = { -1, 1, -2, 2, -2, 2, -1, 1 };
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int k = Integer.parseInt(br.readLine());
String input[] = br.readLine().split(" ");
m = Integer.parseInt(input[0]);
n = Integer.parseInt(input[1]);
board = new int[n][m];
for (int i = 0; i < n; i++) {
input = br.readLine().split(" ");
for (int j = 0; j < m; j++) {
board[i][j] = Integer.parseInt(input[j]);
}
}
bw.write(bfs(k) + "\n");
br.close();
bw.close();
}
static boolean isrange(int y, int x) {
return 0 <= y && y < n && 0 <= x && x < m;
}
static int bfs(int k) {
boolean visit[][][] = new boolean[n][m][k + 1];
Queue<Point> q = new LinkedList<Point>();
q.add(new Point(0, 0, 0, k));
visit[0][0][k] = true;
while (!q.isEmpty()) {
int y = q.peek().y;
int x = q.peek().x;
int cnt = q.peek().cnt;
k = q.poll().k;
if (y == n - 1 && x == m - 1)
return cnt;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (isrange(ny, nx)) {
if (!visit[ny][nx][k] && board[ny][nx] == 0) {
visit[ny][nx][k] = true;
q.add(new Point(ny, nx, cnt + 1, k));
}
}
}
if (k > 0) {
for (int i = 0; i < 8; i++) {
int ny = y + hy[i];
int nx = x + hx[i];
if (isrange(ny, nx)) {
if (!visit[ny][nx][k - 1] && board[ny][nx] == 0) {
visit[ny][nx][k - 1] = true;
q.add(new Point(ny, nx, cnt + 1, k - 1));
}
}
}
}
}
return -1;
}
}
class Point {
int y, x, cnt, k;
public Point(int y, int x, int cnt, int k) {
super();
this.y = y;
this.x = x;
this.cnt = cnt;
this.k = k;
}
}
|
cs |
궁금한점 혹은 모르는점이 있다면 언제든 댓글을 이용해주시길 부탁드립니당.
'백준' 카테고리의 다른 글
| 백준 3687 성냥개비 (0) | 2021.04.23 |
|---|---|
| 백준 17130 토끼가 정보섬에 올라온 이유 (0) | 2021.04.16 |
| 백준 2931 가스관 (0) | 2021.04.05 |
| 백준 14888 연산자 끼워넣기 (0) | 2021.02.17 |
| 백준 14502 연구소 (0) | 2021.02.17 |
