반응형
BFS를 사용하여 최단 시간을 찾는 문제이다.
단, 일반적인 BFS와는 다르게 움직일때 두가지(일반, 말) 방법으로 움직이게 되고, 말처럼 움직이는 경우는 횟수가 제한이된다. 따라서 visit 배열을 3차원으로 visit[행][열][말처럼 움직일수 있는 남은 횟수] 로 만들어서, 구한다.
그리고 queue에서 poll 할때 도착지점인 경우 result와의 최솟값을 비교해주어서 답을 구한다.
|
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
|
package chap05;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main_bj_1600_말이되고픈원숭이_re {
static int[] di= {-1,0,1,0};
static int[] dj= {0,1,0,-1};
static int K,R,C;
static boolean[][][] visit;
static int[][] map;
static int result;
static Queue<Pos> queue;
static class Pos{
int i,j,horse,sec;
public Pos(int i,int j,int h,int s) {
this.i=i;this.j=j;horse=h;sec=s;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=null;
K=Integer.parseInt(br.readLine());
st=new StringTokenizer(br.readLine());
C=Integer.parseInt(st.nextToken());
R=Integer.parseInt(st.nextToken());
visit=new boolean[R][C][K+1];
map=new int[R][C];
queue=new LinkedList<>();
for(int i=0;i<R;i++) {
st= new StringTokenizer(br.readLine());
for(int j=0;j<C;j++) {
map[i][j]=Integer.parseInt(st.nextToken());
}
}
result=Integer.MAX_VALUE;
bfs();
if(result==Integer.MAX_VALUE)
System.out.println(-1);
else
System.out.println(result);
}
static Pos moveLikeHorse(int i,int j,int dir) {
int nextI=0;
int nextJ=0;
if(dir==0) {
nextI=i-1; nextJ=j-2;
}else if(dir==1) {
nextI=i-2; nextJ=j-1;
}else if(dir==2) {
nextI=i-2; nextJ=j+1;
}else if(dir==3) {
nextI=i-1; nextJ=j+2;
}else if(dir==4) {
nextI=i+1; nextJ=j+2;
}else if(dir==5) {
nextI=i+2; nextJ=j+1;
}else if(dir==6) {
nextI=i+2; nextJ=j-1;
}else if(dir==7) {
nextI=i+1; nextJ=j-2;
}
return new Pos(nextI, nextJ, 0, 0);
}
static void bfs() {
visit[0][0][K]=true;
while(!queue.isEmpty()) {
Pos cur= queue.poll();
// System.out.println("cur는 " +cur.i +","+cur.j+" sec : "+cur.sec+ "," +cur.horse);
if(cur.i==R-1 && cur.j == C-1) {
result=Math.min(result, cur.sec);
}
for(int dir=0;dir<4;dir++) {
int nextI=cur.i + di[dir];
int nextJ=cur.j + dj[dir];
if(nextI<0 || nextI>=R || nextJ<0 || nextJ>=C)
continue;
if(map[nextI][nextJ] == 0 && visit[nextI][nextJ][0]==false) {
visit[nextI][nextJ][0]=true;
}
}
}else { //말처럼 움직일수 있는 횟수가 남은 경우
for(int dir=0;dir<8;dir++) {
Pos next=moveLikeHorse(cur.i, cur.j, dir);
int nextI=next.i; int nextJ=next.j;
if(nextI<0 || nextI>=R || nextJ<0 || nextJ>=C)
continue;
}
}
for(int dir=0;dir<4;dir++) {
int nextI=cur.i + di[dir];
int nextJ=cur.j + dj[dir];
if(nextI<0 || nextI>=R || nextJ<0 || nextJ>=C)
continue;
}
}
}
}
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
반응형
'Algorithm' 카테고리의 다른 글
| [BOJ] 2146. 다리 만들기 (0) | 2020.03.21 |
|---|---|
| [BOJ] 12851. 숨바꼭질2 (0) | 2020.03.18 |
| [BOJ] 13549. 숨바꼭질3 (0) | 2020.03.15 |
| [BOJ] 2206. 벽 부수고 이동하기 (0) | 2020.03.15 |
| [BOJ] 7576. 토마토 (2) | 2020.03.10 |