카테고리 없음
백준 14442 - 벽부수고 이동하기 2
jin_j_i_n
2021. 5. 10. 19:23
벽 부술 수 있는 개수에 따라 이동할지 말지 정하는 문제
visit 배열을 3차원으로 선언해줘서 z 가 k 미만일때는 벽을 부수고 이동할. 수 있고 , k일때는 이동하지 못한다.
반례라 하면 엣지케이스를 봐야할 것 같다
올 상반기 코테 보면서 가장 뼈저리게 느끼는 부분.....히든케이스는 스스로 잡아야하낟
이번 히든케이스는 배열 크기가 1 1 일때 답은 1이지만 , 출력은 -1로 나왔었음
|
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
|
package algorithm;
import java.io.*;
import java.util.*;
public class B14442 {
static boolean[][][] visit;
static int n; static int m; static int k;
static int[][][] count;
static int[] dx = {0,0,1,-1};
static int[] dy = {1,-1,0,0};
static int[][] board;
public static class Point{
int x; int y; int z;
public Point(int x , int y , int z) {
this.x = x; this.y =y ; this.z = z ;
}
}
public static boolean check(int x , int y) {
return x >= 0 && x < n && y >= 0 && y < m ;
}
public static void bfs (Point p) {
Queue<Point> que = new LinkedList<Point>();
visit[p.x][p.y][p.z]= true;
que.add(p);
while(!que.isEmpty()) {
Point tmp = que.poll();
int x = tmp.x; int y = tmp.y ; int z = tmp.z;
for(int i=0 ; i<4 ; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(check(nx,ny)) {
//벽이 아니면 그냥 이동
if(board[nx][ny] == 0 && !visit[nx][ny][z]) {
visit[nx][ny][z] = true;
count[nx][ny][z] = count[x][y][z] + 1;
que.add(new Point(nx,ny,z));
}else {
if( z < k && !visit[nx][ny][z+1]) {
//벽부수고 이동 가능
visit[nx][ny][z+1] = true;
count[nx][ny][z+1] = count[x][y][z] + 1;
que.add(new Point(nx,ny,z+1));
}else if ( z == k ) {
//이동 불가능
continue;
}
}
}
}
}
}
public static void main(String[] args)throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] inputs = br.readLine().split(" ");
n = Integer.parseInt(inputs[0]);
m = Integer.parseInt(inputs[1]);
k = Integer.parseInt(inputs[2]);
board = new int[n][m];
visit = new boolean[n][m][k+1];
count = new int[n][m][k+1];
for(int i=0 ; i<n ; i++) {
inputs = br.readLine().split("");
for(int j = 0 ; j< m ; j++) {
board[i][j] = Integer.parseInt(inputs[j]);
}
}
bfs(new Point(0,0,0));
int min = Integer.MAX_VALUE;
for(int i =0 ; i<= k ;i++) {
if(count[n-1][m-1][i] != 0 ) {
min = Math.min(min, count[n-1][m-1][i]);
}
}
if( min == Integer.MAX_VALUE ) {
if(n == 1&& m == 1) {
System.out.println(1);
}else {
System.out.println(-1);
}
}else {
System.out.println(min+1);
}
}
}
|
cs |