알고리즘/SW Expert Academy
1953.탈주범 검거
IMyoungho
2020. 7. 28. 00:36
이번에 풀어볼 문제는 SW Expert의 탈주범 검거이다.
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
이러한 유형의 문제의 난이도는 사람마다 다르겠지만 쉬운 편에 속한다고 생각한다.
그 이유는 문제에서 요구하는 형태들을 정확하게 구현하기만 하면 되기 때문이다.
이번 문제에서도 별다른 고민없이 그저 해당 파이프가 주어졌을 때 어떤식으로 움직이게 되는지만
구현하는 것과 DFS만 구현하면 굉장히 쉽게 풀 수 있는 문제이다.
구현에서 신경써야할 부분은 그저 어떠한 파이프가 주어졌을 때, 탈주범이 갈 수 있느냐 없느냐만 주의해주면 된다.
=> 단순한 문제이기 때문에 따로 설명은 생략하도록 하겠다. 갈 수 있는지, 없는지에 대한 예외 조건만 신경쓰자!
=> 코드는 중복되는 부분을 줄여서 단순화 할 수 있다. 근데 굳이 필요는 없다고 생각한다.(이건 본인마음대로)
< Code 설명 >
|
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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
|
#pragma warning(disable:4996) #include <iostream>
#include <string.h>
#include <deque>
#define MAX 51
using namespace std;
int T, N, M, R, C, L, ans;
int map[MAX][MAX];
bool check[MAX][MAX];
deque<pair<int, int>>tmp; // DFS를 위한 deque
void search(){
int x, y;
for (int z = 1; z < L; z++){ // 이미 첫 1초에 맨홀에서 나온것도 시간에 포함이므로 1초부터 시작
int size = tmp.size(); // 이 부분이 중요! 1초에 얼만큼 가는지 체크하는 변수가 됨
while (size--){
x = tmp.front().first;
y = tmp.front().second;
tmp.pop_front();
if (map[x][y] == 1){ // 파이프의 모양에 따라 갈 수 있는 곳과 없는 곳을 구별하는 로직을 구현하면됨( 1 ~ 7 번 형태의 파이프 각각 구현 )
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
for (int i = 0; i < 4; i++){
int ax = x + dx[i];
int ay = y + dy[i];
if (ax < 0 || ay < 0 || ax >= N || ay >= M)
continue;
if ((dx[i] == 0 && dy[i] == -1) && (map[ax][ay] == 2 || map[ax][ay] == 7 || map[ax][ay] == 6))
continue;
else if ((dx[i] == 0 && dy[i] == 1) && (map[ax][ay] == 2 || map[ax][ay] == 4 || map[ax][ay] == 5))
continue;
else if ((dx[i] == -1 && dy[i] == 0) && (map[ax][ay] == 4 || map[ax][ay] == 7 || map[ax][ay] == 3))
continue;
else if ((dx[i] == 1 && dy[i] == 0) && (map[ax][ay] == 5 || map[ax][ay] == 6 || map[ax][ay] == 3))
continue;
if (map[ax][ay] && !check[ax][ay]){ // DFS를 하기위함임
ans += 1;
check[ax][ay] = true;
tmp.push_back(make_pair(ax, ay));
}
}
}
else if (map[x][y] == 2){
int dx[2] = { -1, 1 };
int dy[2] = { 0, 0 };
for (int i = 0; i < 2; i++){
int ax = x + dx[i];
int ay = y + dy[i];
if (ax < 0 || ay < 0 || ax >= N || ay >= M)
continue;
if ((dx[i] == -1 && dy[i] == 0) && (map[ax][ay] == 4 || map[ax][ay] == 7 || map[ax][ay] == 3))
continue;
else if ((dx[i] == 1 && dy[i] == 0) && (map[ax][ay] == 5 || map[ax][ay] == 6 || map[ax][ay] == 3))
continue;
if (map[ax][ay] > 0 && !check[ax][ay]){
ans += 1;
check[ax][ay] = true;
tmp.push_back(make_pair(ax, ay));
}
}
}
else if (map[x][y] == 3){
int dx[2] = { 0, 0 };
int dy[2] = { -1, 1 };
for (int i = 0; i < 2; i++){
int ax = x + dx[i];
int ay = y + dy[i];
if (ax < 0 || ay < 0 || ax >= N || ay >= M)
continue;
if ((dx[i] == 0 && dy[i] == -1) && (map[ax][ay] == 6 || map[ax][ay] == 7 || map[ax][ay] == 2))
continue;
else if ((dx[i] == 0 && dy[i] == 1) && (map[ax][ay] == 4 || map[ax][ay] == 5 || map[ax][ay] == 2))
continue;
if (map[ax][ay] > 0 && !check[ax][ay]){
ans += 1;
check[ax][ay] = true;
tmp.push_back(make_pair(ax, ay));
}
}
}
else if (map[x][y] == 4){
int dx[2] = { -1, 0 };
int dy[2] = { 0, 1 };
for (int i = 0; i < 2; i++){
int ax = x + dx[i];
int ay = y + dy[i];
if (ax < 0 || ay < 0 || ax >= N || ay >= M)
continue;
if ((dx[i] == -1 && dy[i] == 0) && (map[ax][ay] == 4 || map[ax][ay] == 7 || map[ax][ay] == 3))
continue;
else if ((dx[i] == 0 && dy[i] == 1) && (map[ax][ay] == 2 || map[ax][ay] == 4 || map[ax][ay] == 5))
continue;
if (map[ax][ay] > 0 && !check[ax][ay]){
ans += 1;
check[ax][ay] = true;
tmp.push_back(make_pair(ax, ay));
}
}
}
else if (map[x][y] == 5){
int dx[2] = { 1, 0 };
int dy[2] = { 0, 1 };
for (int i = 0; i < 2; i++){
int ax = x + dx[i];
int ay = y + dy[i];
if (ax < 0 || ay < 0 || ax >= N || ay >= M)
continue;
if ((dx[i] == 0 && dy[i] == 1) && (map[ax][ay] == 5 || map[ax][ay] == 2 || map[ax][ay] == 4))
continue;
else if ((dx[i] == 1 && dy[i] == 0) && (map[ax][ay] == 5 || map[ax][ay] == 3 || map[ax][ay] == 6))
continue;
if (map[ax][ay] > 0 && !check[ax][ay]){
ans += 1;
check[ax][ay] = true;
tmp.push_back(make_pair(ax, ay));
}
}
}
else if (map[x][y] == 6){
int dx[2] = { 1, 0 };
int dy[2] = { 0, -1 };
for (int i = 0; i < 2; i++){
int ax = x + dx[i];
int ay = y + dy[i];
if (ax < 0 || ay < 0 || ax >= N || ay >= M)
continue;
if ((dx[i] == 0 && dy[i] == -1) && (map[ax][ay] == 2 || map[ax][ay] == 6 || map[ax][ay] == 7))
continue;
else if ((dx[i] == 1 && dy[i] == 0) && (map[ax][ay] == 3 || map[ax][ay] == 5 || map[ax][ay] == 6))
continue;
if (map[ax][ay] > 0 && !check[ax][ay]){
ans += 1;
check[ax][ay] = true;
tmp.push_back(make_pair(ax, ay));
}
}
}
else if (map[x][y] == 7){
int dx[2] = { -1, 0 };
int dy[2] = { 0, -1 };
for (int i = 0; i < 2; i++){
int ax = x + dx[i];
int ay = y + dy[i];
if (ax < 0 || ay < 0 || ax >= N || ay >= M)
continue;
if ((dx[i] == -1 && dy[i] == 0) && (map[ax][ay] == 7 || map[ax][ay] == 3 || map[ax][ay] == 4))
continue;
else if ((dx[i] == 0 && dy[i] == -1) && (map[ax][ay] == 7 || map[ax][ay] == 6 || map[ax][ay] == 2))
continue;
if (map[ax][ay] > 0 && !check[ax][ay]){
ans += 1;
check[ax][ay] = true;
tmp.push_back(make_pair(ax, ay));
}
}
}
}
}
}
void init(){ // 초기화
memset(map, 0, sizeof(map))
memset(check, 0, sizeof(check));
tmp.clear();
}
int main() {
freopen("1953.txt", "r", stdin);
cin >> T;
for (int z = 1; z <= T; z++){
init();
cin >> N >> M >> R >> C >> L;
for (int i = 0; i < N; i++){
for (int j = 0; j < M; j++){
cin >> map[i][j];
}
}
ans = 1; // 맨홀에서 나온 것부터 탈주범이 있을 수 있는 경우의 수이므로
check[R][C] = true;
tmp.push_back(make_pair(R, C));
search();
cout << "#" << z << " " << ans << endl;
}
return 0;
}
|
cs |
반응형