반응형
BFS를 두번 사용할 계획을 세웠다.
첫번째 BFS를 통하여 모든 악마를 찾아 스킬이 도달하는 최단시간을 visitForDevil 배열에 저장해주었다. 그 후 두번째 BFS를 통해 S의 위치를 찾아 S가 n초 후에 도달할 수 있는 .의 위치에서 visitForDevil의 시간을 비교하여 도달여부를 결정하였다. 이런식으로 D를 찾으면 종료하였고, 못 찾으면 GameOver를 해주었다.
그렇지만 두번 BFS를 도는 방법 말고도, 구분자를 사용하여 악마와 S를 하나의 BFS에서 처리할 수 있는 방법도 있다.(단, 악마가 queue에 S보다 먼저 들어가 있어야함). 이 방법은 코드를 더 짧게 해주고, 시간도 더 줄여줄 수 있다.
|
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
141
142
143
144
145
146
147
148
|
package swea;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Solution_d5_7793_오나의여신님 {
static char[][] map;
static int[][] visitForDevil;
static int[][] visit;
static int[] di = {-1,0,1,0};
static int[] dj = {0,1,0,-1};
static boolean find;
static int result;
static int N, M;
static Queue<Pos> queue;
static class Pos{
int i,j;
int dis;
public Pos(int i, int j,int dis) {
this.i=i;
this.j=j;
this.dis=dis;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int T= Integer.parseInt(br.readLine());
for(int tc=1;tc<=T;tc++) {
st=new StringTokenizer(br.readLine());
N=Integer.parseInt(st.nextToken());
M=Integer.parseInt(st.nextToken());
map=new char[N][M];
for(int i=0;i<N;i++) {
String str =br.readLine();
for(int j=0;j<M;j++) {
map[i][j]=str.charAt(j);
}
}
visitForDevil=new int[N][M];
visit=new int[N][M];
queue = new LinkedList<>();
findDevilSkill();
find=false;
result = 0;
findExit();
if(result!=0)
System.out.println("#"+tc+" "+result);
else
System.out.println("#"+tc+" GAME OVER");
}
}
static void findDevilSkill() {
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
if(map[i][j]=='*') { //악마를 찾은 경우
while(!queue.isEmpty()) {
Pos cur = queue.poll();
for(int dir=0;dir<4;dir++) {
int nextI = cur.i+ di[dir];
int nextJ = cur.j+ dj[dir];
if(nextI<0 || nextI>=N || nextJ<0 || nextJ>=M)
continue;
if(map[nextI][nextJ]=='.') {
if(visitForDevil[nextI][nextJ]==0) {
}else {
}
}
}
}
}
}
}
}
}
static void findExit() {
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
if(map[i][j]=='S') {
while(!queue.isEmpty()) {
Pos cur = queue.poll();
for(int dir=0;dir<4;dir++) {
int nextI=cur.i+di[dir];
int nextJ=cur.j+dj[dir];
if(nextI<0 || nextI>=N || nextJ<0 || nextJ>=M)
continue;
if(map[nextI][nextJ]=='D') {
return;
}
if(map[nextI][nextJ]=='.' && visit[nextI][nextJ]==0) {
if(visitForDevil[nextI][nextJ]==0) {
}else {
}
}
}
}
}
}
}
}
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
반응형
'Algorithm' 카테고리의 다른 글
| [BOJ] 12851. 숨바꼭질2 (0) | 2020.03.18 |
|---|---|
| [BOJ] 1600. 말이 되고픈 원숭이 (0) | 2020.03.18 |
| [BOJ] 13549. 숨바꼭질3 (0) | 2020.03.15 |
| [BOJ] 2206. 벽 부수고 이동하기 (0) | 2020.03.15 |
| [BOJ] 7576. 토마토 (2) | 2020.03.10 |