https://www.acmicpc.net/problem/1938
1938번: 통나무 옮기기
첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4<=N<=50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문자 사이에는 빈칸이 없다. 통나무와 최종 위치의 개수는 1개이다.
www.acmicpc.net
처음 주어진 통나무의 위치로부터 가능한 동작(U, D, R, L, T)을 모두 사용하여 도착지점까지 이동하면 된다.
이동할 때마다 매번 U, D, R, D, T를 해보고 이동이 가능하다면 동작수를 증가시켜서 이동하면 된다.
이동했을 때 범위를 벗어나거나 / 잘려지지 않은 나무가 있는 경우가 아니라면 이동 가능하다.
최소 동작수를 구해야 하므로 이미 갔던 좌표에도 다시 갈 필요가 없다.
하지만 통나무의 방향이 가로방향으로 온 것과 세로 방향으로 온 것은 구분해주어야 한다.
특히, 회전(T)을 할 때에는 3X3 정사각형 위치에 나무가 있거나 범위를 벗어나지 않는지 모두 확인해주어야 한다.
처음 입력받을 때 처음 통나무 위치의 좌표( pair<int, int> start[3] )와
이동할 위치의 좌표( pair<int, int> dest[3] )를 각각 배열에 저장한다.
그리고 실제 이동은 통나무의 길이는 3으로 정해져 있으므로 중심점의 좌표만 이용하여 이동한다.
처음 방향은 이어진 두 좌표가 같은 x좌표라면 (같은 행에 있다면) 가로 방향이고
그렇지 않다면(다른 x좌표 == 다른 행) 세로 방향이다.
이 중심점의 좌표와 방향을 이용하여 통나무를 이동시킨다.
이동할 통나무의 정보는 Tree라는 구조체를 만들어서 저장하였다.
Tree는 x좌표와 y좌표 dir(방향), cnt(동작수)를 가지고 있다.
방향은 0이면 가로방향 1이면 세로 방향으로 해놓았다.
이동이 가능할 때마다 이동할 중심 좌표의 위치와, 방향, 이전 동작수 +1을 해서 새로 큐에 넣어주면 된다.
최소 동작 수로 이동시키기 위해서 BFS를 사용하는데
방향이 가로방향인지 세로 방향인지에 따라 이동할 위치를 검사할 조건이 다르므로 각각 구현해준다.
이동한 위치의 중심 좌표가 목표한 지점의 중심 좌표와 같고 방향도 같다면 목표지점에 도착한 것이므로 그때의 동작수가 정답이다.
|
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
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
|
#include <iostream>
#include <queue>
using namespace std;
int n;
char map[50][50];
pair<int, int> start[3];
pair<int, int> dest[3];
//도착지점의 방향
int destDir;
int dx[] = { -1,-1,-1,0,0,1,1,1 };
int dy[] = { -1,0,1,-1,1,-1,0,1 };
//visit[x][y][0] = 가로방향인 상태에서 x,y 에 방문
//visit[x][y][1] = 세로방향인 상태에서 x,y에 방문
bool visit[50][50][2];
struct Tree {
int x, y;
int dir;
int cnt;
Tree(int i, int j, int d, int c) {
x = i;
y = j;
dir = d;
cnt = c;
}
};
bool turn(int x, int y) {
int nx, ny;
//중심점에 인접한 8방향을 검사
for (int k = 0; k < 8; k++) {
nx = x + dx[k];
ny = y + dy[k];
//범위를 벗어나면 회전 불가능
if (nx < 0 || ny < 0 || nx >= n || ny >= n) return false;
//나무 있으면 회전 불가능
if (map[nx][ny] == '1') return false;
}
//위의 조건에서 걸리지 않으면 회전 가능
return true;
}
int solve(int x, int y, int dir) {
queue<Tree> q;
//x좌표, y좌표, 방향, 동작수
q.push(Tree(x, y, dir, 0));
visit[x][y][dir] = true;
int cnt;
while (!q.empty()) {
x = q.front().x;
y = q.front().y;
dir = q.front().dir;
cnt = q.front().cnt;
q.pop();
//도착지점의 중심좌표와 방향이 같다.
if (x == dest[1].first && y == dest[1].second && dir == destDir) return cnt;
int nx, ny;
if (dir == 0) {
//통나무의 현재 방향이 가로방향
//U
nx = x - 1;
ny = y;
//범위와 방문 체크
if (nx >= 0 && !visit[nx][ny][dir]) {
//이동할 위치에 나무가 있는지 체크
if (map[nx][ny] == '0' && map[nx][ny - 1] == '0' && map[nx][ny + 1] == '0') {
visit[nx][ny][dir] = true;
q.push(Tree(nx, ny, dir, cnt + 1));
}
}
//D
nx = x + 1;
ny = y;
if (nx < n && !visit[nx][ny][dir]) {
if (map[nx][ny] == '0' && map[nx][ny - 1] == '0' && map[nx][ny + 1] == '0') {
visit[nx][ny][dir] = true;
q.push(Tree(nx, ny, dir, cnt + 1));
}
}
//L
nx = x;
ny = y - 1;
if (ny -1 >= 0 && !visit[nx][ny][dir]) {
if (map[nx][ny - 1] == '0') {
visit[nx][ny][dir] = true;
q.push(Tree(nx, ny, dir, cnt + 1));
}
}
//R
nx = x;
ny = y + 1;
if (ny + 1 < n && !visit[nx][ny][dir]) {
if (map[nx][ny + 1] == '0') {
visit[nx][ny][dir] = true;
q.push(Tree(nx, ny, dir, cnt + 1));
}
}
//T
if (turn(x,y) && !visit[x][y][1]) {
q.push(Tree(x, y, 1, cnt + 1));
visit[x][y][1] = true;
}
}
else {
//세로 방향
//U
nx = x - 1;
ny = y;
if (nx - 1 >= 0 && !visit[nx][ny][dir]) {
if (map[nx - 1][ny] == '0') {
q.push(Tree(nx, ny, dir, cnt + 1));
visit[nx][ny][dir] = true;
}
}
//D
nx = x + 1;
ny = y;
if (nx + 1 < n && !visit[nx][ny][dir]) {
if (map[nx + 1][ny] == '0') {
q.push(Tree(nx, ny, dir, cnt + 1));
visit[nx][ny][dir] = true;
}
}
//L
nx = x;
ny = y - 1;
if (ny >= 0 && !visit[nx][ny][dir]) {
if (map[nx - 1][ny] == '0' && map[nx][ny] == '0' && map[nx + 1][ny] == '0') {
q.push(Tree(nx, ny, dir, cnt + 1));
visit[nx][ny][dir] = true;
}
}
//R
nx = x;
ny = y + 1;
if (ny < n && !visit[nx][ny][dir]) {
if (map[nx - 1][ny] == '0' && map[nx][ny] == '0' && map[nx + 1][ny] == '0') {
q.push(Tree(nx, ny, dir, cnt + 1));
visit[nx][ny][dir] = true;
}
}
//T
if (turn(x, y) && !visit[x][y][0]) {
q.push(Tree(x, y, 0, cnt + 1));
visit[x][y][0] = true;
}
}
}
return 0;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
int k = 0;
int l = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> map[i][j];
if (map[i][j] == 'B') {
start[k].first = i;
start[k].second = j;
k++;
map[i][j] = '0';
}
else if (map[i][j] == 'E') {
dest[l].first = i;
dest[l].second = j;
l++;
map[i][j] = '0';
}
}
}
//도착지점의 방향
//첫번째와 두번째 위치의 x좌표가 같으면 가로방향
//가로 방향 : 0 , 세로 방향 : 1
if (dest[0].first == dest[1].first) destDir = 0;
else destDir = 1;
//시작위치의 방향
//첫번째와 두번째 위치의 x좌표가 같으면 가로방향
//가로 방향 : 0 , 세로 방향 : 1
if (start[0].first == start[1].first) cout << solve(start[1].first, start[1].second, 0);
else cout << solve(start[1].first, start[1].second, 1);
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 1331. 나이트 투어 (0) | 2020.03.03 |
|---|---|
| [BOJ] 4179. 불! (0) | 2020.02.17 |
| [BOJ] 17780. 새로운 게임 (0) | 2020.02.03 |
| [BOJ] 17837. 새로운 게임 2 (0) | 2020.02.03 |
| [BOJ] 1600. 말이 되고픈 원숭이 (0) | 2020.02.01 |