728x90
https://www.acmicpc.net/problem/3055
3055번: 탈출
사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제
www.acmicpc.net
// 코드 : 통과 실패
|
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
|
import java.util.*;
import java.io.*;
class Main{
static int R, C;
static int[][] arr;
static int[] dp;
static boolean[][] visited;
static boolean[][] wVisited;
static int[] startPoint = new int[2];
static int[] goalPoint = new int[2];
static int[] waterPoint = new int[2];
static final int[][] DIR = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
static Deque<int[]> sbfs(Deque<int[]> sDeq) {
Deque<int[]> retDeq = new ArrayDeque<>();
while(!sDeq.isEmpty()) {
int[] pos = sDeq.pop();
for(int i=0; i<4; ++i) {
int ny = pos[0] + DIR[i][0];
int nx = pos[1] + DIR[i][1];
if(ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
if(!visited[ny][nx] && arr[ny][nx] == 0 || arr[ny][nx] == -3 && arr[ny][nx] != -4) {
visited[ny][nx] = true;
arr[ny][nx] = -1;
retDeq.add(new int[]{ny, nx});
}
}
}
return retDeq;
}
static Deque<int[]> wbfs(Deque<int[]> wDeq) {
Deque<int[]> retDeq = new ArrayDeque<>();
while(!wDeq.isEmpty()) {
int[] pos = wDeq.pop();
for(int i=0; i<4; ++i) {
int ny = pos[0] + DIR[i][0];
int nx = pos[1] + DIR[i][1];
if(ny < 0 || ny >= R || nx < 0 || nx >= C || (ny == goalPoint[0] && nx == goalPoint[1])) continue;
if(!wVisited[ny][nx] && arr[ny][nx] != -3 && arr[ny][nx] != -4) {
wVisited[ny][nx] = true;
arr[ny][nx] = -2;
retDeq.add(new int[]{ny, nx});
}
}
}
return retDeq;
}
public static void main(String[] args) throws Exception {
// Please Enter Your Code Here
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
arr = new int[R][C];
visited = new boolean[R][C];
wVisited = new boolean[R][C];
for(int row=0; row<R; ++row) {
String[] str = br.readLine().split("");
for(int col=0; col<C; ++col) {
if(str[col].equals("D")) {
arr[row][col] = -3;
goalPoint[0] = row;
goalPoint[1] = col;
}
else if(str[col].equals("*")) {
arr[row][col] = -2;
waterPoint[0] = row;
waterPoint[1] = col;
}
else if(str[col].equals("S")) {
arr[row][col] = -1;
startPoint[0] = row;
startPoint[1] = col;
}
else if(str[col].equals("X")) {
arr[row][col] = -4;
}
else arr[row][col] = 0;
}
}
Deque<int[]> sDeq = new ArrayDeque<>();
sDeq.add(startPoint);
visited[startPoint[0]][startPoint[1]] = true;
Deque<int[]> wDeq = new ArrayDeque<>();
wDeq.add(waterPoint);
wVisited[waterPoint[0]][waterPoint[1]] = true;
int cnt = 0;
while(!wDeq.isEmpty() || !sDeq.isEmpty()) {
wDeq = wbfs(wDeq);
sDeq = sbfs(sDeq);
if(!sDeq.isEmpty()) cnt++;
}
if(arr[goalPoint[0]][goalPoint[1]] == -3) bw.write("KAKTUS");
else bw.write(String.valueOf(cnt));
br.close();
bw.flush();
bw.close();
}
}
|
cs |
// 코드 : 통과--
// 실수1 : 물 좌표가 여러개인데 한개일거라 가정하고 해서 틀렸다.
// 실수2 : 목적지 도달했을 때 탈출을 안해줬었다.
|
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
|
import java.util.*;
import java.io.*;
class Main{
static int R, C;
static int[][] arr;
static boolean[][] visited;
static boolean[][] wVisited;
static int[] startPoint = new int[2];
static int[] goalPoint = new int[2];
static final int[][] DIR = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
static Deque<int[]> sbfs(Deque<int[]> sDeq) {
Deque<int[]> retDeq = new ArrayDeque<>();
while(!sDeq.isEmpty()) {
int[] pos = sDeq.pop();
for(int i=0; i<4; ++i) {
int ny = pos[0] + DIR[i][0];
int nx = pos[1] + DIR[i][1];
if(ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
if(!visited[ny][nx] && arr[ny][nx] == 0 || arr[ny][nx] == -3 && arr[ny][nx] != -4) {
visited[ny][nx] = true;
arr[ny][nx] = -1;
if(ny == goalPoint[0] && nx == goalPoint[1]) return null;
retDeq.add(new int[]{ny, nx});
}
}
}
return retDeq;
}
static Deque<int[]> wbfs(Deque<int[]> wDeq) {
Deque<int[]> retDeq = new ArrayDeque<>();
while(!wDeq.isEmpty()) {
int[] pos = wDeq.pop();
for(int i=0; i<4; ++i) {
int ny = pos[0] + DIR[i][0];
int nx = pos[1] + DIR[i][1];
if(ny < 0 || ny >= R || nx < 0 || nx >= C || (ny == goalPoint[0] && nx == goalPoint[1])) continue;
if(!wVisited[ny][nx] && arr[ny][nx] != -3 && arr[ny][nx] != -4) {
wVisited[ny][nx] = true;
arr[ny][nx] = -2;
retDeq.add(new int[]{ny, nx});
}
}
}
return retDeq;
}
public static void main(String[] args) throws Exception {
// Please Enter Your Code Here
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
arr = new int[R][C];
visited = new boolean[R][C];
wVisited = new boolean[R][C];
Deque<int[]> wDeq = new ArrayDeque<>();
for(int row=0; row<R; ++row) {
String[] str = br.readLine().split("");
for(int col=0; col<C; ++col) {
if(str[col].equals("D")) {
arr[row][col] = -3;
goalPoint[0] = row;
goalPoint[1] = col;
}
else if(str[col].equals("*")) {
arr[row][col] = -2;
int[] waterPoint = new int[2];
waterPoint[0] = row;
waterPoint[1] = col;
wDeq.add(waterPoint);
}
else if(str[col].equals("S")) {
arr[row][col] = -1;
startPoint[0] = row;
startPoint[1] = col;
}
else if(str[col].equals("X")) {
arr[row][col] = -4;
}
else arr[row][col] = 0;
}
}
Deque<int[]> sDeq = new ArrayDeque<>();
sDeq.add(startPoint);
visited[startPoint[0]][startPoint[1]] = true;
int cnt = 0;
while(!wDeq.isEmpty() || !sDeq.isEmpty()) {
wDeq = wbfs(wDeq);
sDeq = sbfs(sDeq);
if(sDeq == null) {cnt++; break;}
if(!sDeq.isEmpty()) cnt++;
}
if(arr[goalPoint[0]][goalPoint[1]] == -3) bw.write("KAKTUS");
else bw.write(String.valueOf(cnt));
br.close();
bw.flush();
bw.close();
}
}
|
cs |
반응형
'CS > 알고리즘_문제풀이(자바)' 카테고리의 다른 글
| 포도주 시식 (0) | 2021.10.19 |
|---|---|
| 가장 긴 증가하는 부분 수열 (0) | 2021.10.18 |
| 퇴사 (0) | 2021.10.18 |
| 합 (0) | 2021.10.15 |
| 벽 부수고 이동하기 (0) | 2021.10.15 |