제출 코드
- 사용 알고리즘 :
BFS
기존 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
package gold;
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 G17836_saveThePrincess {
static int N, M, T;
static int[][] map;
static int[] di = {-1, 0, 1, 0};
static int[] dj = {0, 1, 0, -1};
static class Point{
int i, j;
boolean isTaken;
Point(int i, int j, boolean isTaken){
this.i = i;
this.j = j;
this.isTaken = isTaken;
}
}
static String bfs() {
Queue<Point> queue = new LinkedList<Point>();
queue.add(new Point(0, 0, false));
map[0][0] = -1;
for(int t=1; t<=T; t++) {
int size = queue.size();
for(int s=0; s<size; s++) {
Point now = queue.poll();
for(int d=0; d<4; d++) {
int ni = now.i + di[d];
int nj = now.j + dj[d];
if(ni==N-1 && nj==M-1) return t+""; // 공주님 찾기 완료
else if(ni<0 || ni>=N || nj<0 || nj>=M || map[ni][nj]==-2
|| ((!now.isTaken)&&((map[ni][nj]==1)||(map[ni][nj]==-1)))
) continue;
else if(map[ni][nj]==2 || now.isTaken) {
queue.add(new Point(ni, nj, true));
map[ni][nj] = -2;
}
else {
queue.add(new Point(ni, nj, false));
map[ni][nj] = -1;
}
}
}
}
return "Fail";
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
T = Integer.parseInt(st.nextToken());
map = new int[N][M];
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<M; j++) map[i][j] = Integer.parseInt(st.nextToken());
}
System.out.println(bfs());
}
}