https://www.acmicpc.net/problem/1726
1726번: 로봇
많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다. 명령 1. Go k - k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다. 명령 2. Turn dir - dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다. 공장 내 궤
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
|
#include<stdio.h>
#include<queue>
#define NSIZE 101
#define MSIZE 101
using namespace std;
int input[NSIZE][MSIZE];
int chk[5][NSIZE][MSIZE];
int N, M;
int ey, ex, edir;
int dy[] = { 0,0,0,1,-1 };
int dx[] = { 0,1,-1,0,0 };
struct Data {
int y, x, dir, cnt;
};
queue<Data>q;
void init() {
scanf("%d %d", &N, &M);
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
scanf("%d", &input[i][j]);
}
}
for (int i = 0; i < 2; i++) {
scanf("%d %d %d", &ey, &ex, &edir);
if (i == 0) {
q.push({ ey,ex,edir,0 });
}
}
}
void bfs() {
while (!q.empty()) {
Data c = q.front(); q.pop();
if (c.y == ey && c.x == ex && c.dir == edir) {//탈출 조건
printf("%d", c.cnt);
return;
}
for (int k = 1; k <= 3; k++) {
Data n;
n.y =c.y+(dy[c.dir] * k);
n.x =c.x+(dx[c.dir] * k);
n.cnt = c.cnt+1;
n.dir = c.dir;
if (1 > n.y || n.y > N || 1 > n.x || n.x >M||input[n.y][n.x]==1) break;
if (input[n.y][n.x] == 0 && chk[n.dir][n.y][n.x] == 0) {
chk[n.dir][n.y][n.x] = 1;
q.push(n);
}
}
int dir1 = 0, dir2 = 0;
if (c.dir == 1 || c.dir == 2) { dir1 = 3; dir2 = 4; }
if (c.dir == 3 || c.dir == 4) { dir1 = 1; dir2 = 2; }
if (chk[dir1][c.y][c.x] == 0) {
chk[dir1][c.y][c.x] = 1;
q.push({ c.y,c.x,dir1,c.cnt + 1 });
}
if (chk[dir2][c.y][c.x] == 0) {
chk[dir2][c.y][c.x] = 1;
q.push({ c.y,c.x,dir2,c.cnt + 1 });
}
}
}
int main() {
init();
bfs();
return 0;
}
|
로봇은 정말 간단하게 생각하시면 되는데
기존에 bfs는 물체의 방향이 딱히 정해져 있지 않고 현재 위치에서 4방향 위치로 이동을 해야 하면 됐지만
이경우에는 같은 자리더라도 동쪽 방향을 보고 있는 로봇, 서쪽 , 북쪽, 동쪽 이렇게 보고 있는 경우도 생각을 해야 하기
때문에 삼차원 배열을 이용하여 각각을 체크합니다.
왜 삼차원을 쓰냐 의문일 수 있고 너무 어려운 것 아니냐 라는 분은 이렇게 생각해 보시면 좋을 것 같습니다.
기존에는 그냥 위치에서 저렇게 넣어도 됐지만 방향이 있으면 동쪽일 때 3 경우와 서쪽일 때 3개의 방향으로 갈 수 있는
경우가 달라 지기 때문에 하늘색으로 칠한 부분 방향이 동쪽일 때의 체크 서쪽일 때의 체크 방향별로 체크를 해야
정확히 모든 경우를 갈 수 있습니다.
지금은 이해가 안 가시더라도 하시다 보면 당연히 이렇게 해야겠네 라고 느껴질 겁니다.
저도 처음에는 삼차원으로 체크하는 게 두렵더라고요. 하다 보면 느끼지만 한 개의 배열 방이 있는 것 말고는
소스는 비슷합니다.
겨우 if(chk [ny][nx]==0)
와 if(chk [n.dir][n.y][n.x]==0) 차이니까요.
그리고 여기서는
이전에는 한 칸씩만 갈 수 있었다면 최대 3칸까지 갈 수 있으므로 저렇게 dy dx 방향에 1 부터 3곱까지 해서 갈수 있으면 큐에 넣는 방식으로 했습니다.
회전의 경우에도
1번과 2번 방향이면 경우가 3과 4의 방향
3번과 4번 방향이면 경우가 1과 2의 방향
이걸 소스 코드로 구현한 것이 위에 소스입니다. 정말 이렇게 단계를 나눈다면 누구든지 쉽게 풀 수 있는 문제입니다.
오늘은 여기까지이고 다음 문제도 파이팅!!!!
'알고리즘 모음집 > 알고리즘 (Algorithm)' 카테고리의 다른 글
| 백준 9019 DSLR (0) | 2019.09.17 |
|---|---|
| 백준 2638 치즈 (0) | 2019.09.17 |
| 백준 2468 안전영역 (0) | 2019.09.17 |
| 백준 1938 통나무 옮기기 (0) | 2019.09.11 |
| 백준 3987 보이저 1호 (0) | 2019.09.09 |
댓글