문제 URL : swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
문제 접근법 :
탈주범이 L-1시간동안 있을수 있는 장소가 몇개나 되는지 개수를 구하는겁니다.
처음 탈주범은 시간당 1의 거리를 움직일 수 있다. 이내용때문에 테스트 케이스 1번이 이해가 안됐는데
반드시 1의 거리를 움직일 필요없고 멈출수 있다는 뜻도 가능하기때문에 문제 안에있던 그림 1-4가 5개가 나올수 있었더군요 결국엔 모든 방향을 터널을통해 모든방향을 움직움직였던 모든 개수들을 구하면 되는문제입니다.
소스코드를 2개를 드릴게요 처음에는 노가다로 풀었는데 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
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
211
212
213
214
215
216
217
218
219
220
221
222
223
224
|
//By 콩순이냉장고
#include <iostream> #include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int n, m, r, c, l;
int map[50][50];
int dy[8][4] = { { 0, },
{ -1, 1, 0, 0 },
{ -1, 1 },
{ 0, 0 },
{-1,0},
{ 1,0 },
{1,0},
{-1,0}
};
int dx[8][4] = {
{ 0, },
{ 0, 0, -1, 1 },
{ 0, 0 },
{ -1, 1 },
{ 0, 1 },
{ 0, 1 },
{ 0, -1 },
{ 0, -1 },
};
bool isrange(int y, int x){
if (0 <= y&&y < n && 0 <= x&&x < m)
return true;
return false;
}
int bfs(){
int cnt = 0;
int visit[50][50] = { 0 };
queue<pair<int, int>> q;
q.push({ r, c });
visit[r][c] = 1;
int time = 0;
while (!q.empty())
{
int qsize = q.size();
if (time >= l-1 )
break;
while (qsize--){
int y = q.front().first;
int x = q.front().second;
q.pop();
int dir = map[y][x];
for (int i = 0; i < 4; i++)
{
int ny = y + dy[dir][i];
int nx = x + dx[dir][i];
if (isrange(ny, nx)&&!visit[ny][nx]){
if (map[ny][nx] == 0)
continue;
switch (map[y][x]){
case 1:
if (i == 0){
if (map[ny][nx] == 1 || map[ny][nx] == 2 || map[ny][nx] == 5 || map[ny][nx] == 6)
{
q.push({ ny, nx });
visit[ny][nx] = 1;
}
}
else if (i == 1){
if (map[ny][nx] == 1 || map[ny][nx] == 2 || map[ny][nx] == 4 || map[ny][nx] == 7)
{
q.push({ ny, nx });
visit[ny][nx] = 1;
}
}
else if (i == 2){
if (map[ny][nx] == 1 || map[ny][nx] == 3 || map[ny][nx] == 4 || map[ny][nx] == 5)
{
q.push({ ny, nx });
visit[ny][nx] = 1;
}
}
else if (i == 3){
if (map[ny][nx] == 1 || map[ny][nx] == 3 || map[ny][nx] == 6 || map[ny][nx] == 7)
{
q.push({ ny, nx });
visit[ny][nx] = 1;
}
}
break;
case 2:
if (i == 0)
{
if (map[ny][nx] <= 2 || map[ny][nx] == 5 || map[ny][nx] == 6)
{
q.push({ ny, nx });
visit[ny][nx] = 1;
}
}
else if (i == 1){
if (map[ny][nx] <= 2 || map[ny][nx] == 4 || map[ny][nx] == 7)
{
q.push({ ny, nx });
visit[ny][nx] = 1;
}
}
break;
case 3:
if (i == 0){
if (map[ny][nx] == 1 || map[ny][nx] == 3 || map[ny][nx] == 4 || map[ny][nx] == 5)
{
q.push({ ny, nx });
visit[ny][nx] = 1;
}
}
else if (i == 1){
if (map[ny][nx] == 1 || map[ny][nx] == 3 || map[ny][nx] == 6 || map[ny][nx] == 7)
{
q.push({ ny, nx });
visit[ny][nx] = 1;
}
}
break;
case 4:
if (i == 0){
if (map[ny][nx] == 1 || map[ny][nx] == 2 || map[ny][nx] == 5 || map[ny][nx] == 6)
{
q.push({ ny, nx });
visit[ny][nx] = 1;
}
}
else if (i == 1){
if (map[ny][nx] == 1 || map[ny][nx] == 3 || map[ny][nx] == 6 || map[ny][nx] == 7)
{
q.push({ ny, nx });
visit[ny][nx] = 1;
}
}
break;
case 5:
if (i == 0){
if (map[ny][nx] == 1 || map[ny][nx] == 2 || map[ny][nx] == 4 || map[ny][nx] == 7)
{
q.push({ ny, nx });
visit[ny][nx] = 1;
}
}
else if (i == 1){
if (map[ny][nx] == 1 || map[ny][nx] == 3 || map[ny][nx] == 6 || map[ny][nx] == 7)
{
q.push({ ny, nx });
visit[ny][nx] = 1;
}
}
break;
case 6:
if (i == 0){
if (map[ny][nx] == 1 || map[ny][nx] == 2 || map[ny][nx] == 4 || map[ny][nx] == 7)
{
q.push({ ny, nx });
visit[ny][nx] = 1;
}
}
else if (i == 1){
if (map[ny][nx] == 1 || map[ny][nx] == 3 || map[ny][nx] == 4 || map[ny][nx] == 5)
{
q.push({ ny, nx });
visit[ny][nx] = 1;
}
}
break;
case 7:
if (i == 0){
if (map[ny][nx] == 1 || map[ny][nx] == 2 || map[ny][nx] == 5 || map[ny][nx] == 6)
{
q.push({ ny, nx });
visit[ny][nx] = 1;
}
}
else if (i == 1){
if (map[ny][nx] == 1 || map[ny][nx] == 3 || map[ny][nx] == 4 || map[ny][nx] == 5)
{
q.push({ ny, nx });
visit[ny][nx] = 1;
}
}
break;
}
}
}
}
time++;
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (visit[i][j])
cnt++;
}
}
return cnt;
}
void input(){
cin >> n >> m >> r >> c >> l;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> map[i][j];
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int te;
cin >> te;
for (int test = 1; test <= te; test++)
{
memset(map, 0, sizeof(map));
input();
cout << "#" << test << " " << bfs() << "\n";
}
}
|
cs |
소스코드 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
|
//By 콩순이냉장고
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int n, m, r, c, l;
int map[50][50];
int dy[4] = { -1, 0, 1, 0 };//상우하좌
int dx[4] = { 0, 1, 0, -1 };
int dir[8][4]={
{ 0, 0, 0, 0 },
{ 1, 1, 1, 1 },//모든방향이가능
{ 1, 0, 1, 0 },
{ 0, 1, 0, 1 },
{ 1, 1, 0, 0 },
{ 0, 1, 1, 0 },
{ 0, 0, 1, 1 },
{ 1, 0, 0, 1 }
};
bool isrange(int y, int x){
if (0 <= y&&y < n && 0 <= x&&x < m)
return true;
return false;
}
int bfs(){
int cnt = 0;
int visit[50][50] = { 0 };
queue<pair<int, int>> q;
q.push({ r, c });
visit[r][c] = 1;
int time = 0;
while (!q.empty())
{
int qsize = q.size();
if (time >= l-1 )
break;
while (qsize--){
int y = q.front().first;
int x = q.front().second;
int tunnel = map[y][x];
q.pop();
for (int i = 0; i < 4; i++)
{
int ny = y + dy[i];
int nx = x + dx[i];
int ntunnel = map[ny][nx];
if (dir[tunnel][i]&&isrange(ny,nx)&&visit[ny][nx]==0){//현재 1번터널이라고 가정한다면
if (dir[ntunnel][(i + 2) % 4])//윗번 터널이라고 가정할때 아래방향을 가지고있는 터널을 가지고있다면 그녀석은 통과할수있음
{
q.push({ ny, nx });
visit[ny][nx] = 1;
}
}
}
}
time++;
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (visit[i][j])
cnt++;
}
}
return cnt;
}
void input(){
cin >> n >> m >> r >> c >> l;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> map[i][j];
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int te;
cin >> te;
for (int test = 1; test <= te; test++)
{
memset(map, 0, sizeof(map));
input();
cout << "#" << test << " " << bfs() << "\n";
}
}
|
cs |
코드를 줄여보는 방법을 찾느라 애좀 먹었습니다.
질문사항 혹은 모르는것이있다면 언제든지 댓글을 이용해주시길 바랍니다.
'SWEA' 카테고리의 다른 글
| [SWEA] 11545 틱택톰 (0) | 2021.05.25 |
|---|---|
| [SWEA] 1767. [SW Test 샘플문제] 프로세서 연결하기 (0) | 2021.05.20 |
| [SWEA] 5650 핀볼 게임(모의 SW 역량테스트) (0) | 2020.09.30 |
| [SWEA] 1941 등산로 조성(모의 SW 역량테스트) (0) | 2020.09.30 |
| [SWEA] 5653 줄기세포배양(모의 SW 역량테스트) (0) | 2020.09.28 |
