[Jungol] 정올 1006 로봇

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=285

 Input 

5 6

0 0 0 0 0 0

0 1 1 0 1 0

0 1 0 0 0 0

0 0 1 1 1 0

1 0 0 0 0 0

4 2 3

2 4 1

 

 Output 

9

※ 방문 확인: visited[101][101][5]

    → visited[x][y][1~4]: (x, y) 지점을 1~4번 방향으로 방문표시

 

① 로봇은 현재 바라보고 있는 방향에서 1~3칸 전진할 수 있습니다.

1~3칸으로 이동가능한지 확인할 때, 범위를 벗어나거나 중간에 장애물이 벗어나는 경우 break 합니다.

    ex) 1칸 전진했을 때, 장애물을 만난다면 로봇은 2, 3칸 이상 전진도 불가능합니다.

하지만 1칸 전진한 곳이 방문한 곳이라고 해서 2, 3칸 전진하는 지점이 반드시 재방문한 곳은 아니기 때문에 continue

 

② 로봇은 현재 바라보고 있는 방향에서 90° 방향으로 좌/우회전 할 수 있습니다.

방향을 바꿀 때는 현재 자리가 범위를 벗어나거나 장애물이 있는 경우는 아니므로 추가적으로 확인하지 않습니다.

다만, 현재 위치에서 바꾼 방향으로 이미 탐색(방문)한 적이 있는지 확인합니다.

▶ 로봇은 총 5가지 행동 결과가 존재합니다.

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
struct Robot {
    int x, y, dir, level;
}que[100 * 100 * 4], start, end;
 
int dr[] = { 0, 0, 0, 1, -1 };
int dc[] = { 0, 1, -1, 0, 0 };
//             동 서 남 북
int M, N, fr, re;
int map[101][101], visited[101][101][5];
 
void input() {
    scanf("%d %d", &M, &N);
    for (int i = 1; i <= M; ++i) {
        for (int j = 1; j <= N; ++j) {
            scanf("%d", &map[i][j]);
        }
    }
    scanf("%d %d %d", &start.x, &start.y, &start.dir);
    scanf("%d %d %d", &end.x, &end.y, &end.dir);
}
 
int turnLeft(int dir) {
    if (dir == 1) return 4;
    else if (dir == 2) return 3;
    else if (dir == 3) return 1;
    else return 2;
}
 
int turnRight(int dir) {
    if (dir == 1) return 3;
    else if (dir == 2) return 4;
    else if (dir == 3) return 2;
    else return 1;
}
 
int BFS() {
    Robot cur;
 
    que[re++] = { start.x, start.y, start.dir, 0 };
    visited[start.x][start.y][start.dir] = 1;
 
    while (fr < re) {
        cur = que[fr++];
        if (cur.x == end.x && cur.y == end.y && cur.dir == end.dir)
            return cur.level;
 
        // 방향 전환 없이
        for (int dist = 1; dist <= 3; ++dist) {
            int nextX = cur.x + (dr[cur.dir] * dist);
            int nextY = cur.y + (dc[cur.dir] * dist);
 
            // 범위를 벗어나는 경우
            if (nextX < 1 || nextY < 1 || nextX > M || nextY > N)
                break;
            // 중간에 장애물인 경우
            if (map[nextX][nextY] == 1)
                break;
 
            if (visited[nextX][nextY][cur.dir] == 1)
                continue;
 
            visited[nextX][nextY][cur.dir] = 1;
            que[re++] = { nextX, nextY, cur.dir, cur.level + 1 };
        }
 
        int nextDir;
        // Turn Left
        nextDir = turnLeft(cur.dir);
        if (visited[cur.x][cur.y][nextDir] != 1) {
            visited[cur.x][cur.y][nextDir] = 1;
            que[re++] = { cur.x, cur.y, nextDir, cur.level + 1 };
        }
 
        // Turn Right
        nextDir = turnRight(cur.dir);
        if (visited[cur.x][cur.y][nextDir] != 1) {
            visited[cur.x][cur.y][nextDir] = 1;
            que[re++] = { cur.x, cur.y, nextDir, cur.level + 1 };
        }
    }
    return -1;
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    input();
    printf("%d\n", BFS());
}