백준 1726번 로봇 :: 마이구미

이 글은 백준 알고리즘 문제 1726번 "로봇" 을 풀이한다.

본인은 BFS를 통해 문제의 풀이를 설명할 것이다.

문제 링크 - https://www.acmicpc.net/problem/1726

BFS 이해 - http://mygumi.tistory.com/102

많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다.

명령 1. Go k
  - k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다.

명령 2. Turn dir
  - dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다.

공장 내 궤도가 설치되어 있는 상태가 아래와 같이 0과 1로 이루어진 직사각형 모양으로 로봇에게 입력된다. 0은 궤도가 깔려 있어 로봇이 갈 수 있는 지점이고, 1은 궤도가 없어 로봇이 갈 수 없는 지점이다. 로봇이 (4, 2) 지점에서 남쪽을 향하고 있을 때,  이 로봇을 (2, 4) 지점에서 동쪽으로 향하도록 이동시키는 것은 아래와 같이 9번의 명령으로 가능하다.

로봇의 현재 위치와 바라보는 방향이 주어졌을 때, 로봇을 원하는 위치로 이동시키고, 원하는 방향으로 바라보도록 하는데 최소 몇 번의 명령이 필요한지 구하는 프로그램을 작성하시오.

문제에서 정확히 인지해야하는 것은 1, 2, 3 만큼 이동할 수 있고, 90도로 회전할 수 있다는 점이다.

이동에 있어서는, 1칸을 움직일 수 없다면, 2칸, 3칸도 움직일 수 없다.

2칸을 움직일 수 없다면, 3칸을 움직일 수 없다.

다음과 같이 위로 1,2,3 이동할 경우가 있기 때문에, 정확히 벽의 존재를 파악해야한다.

0
1
0
R

회전에 있어서는, 회전은 왼쪽 오른쪽 각 90도로 회전한다는 것이다.

만약 북쪽에서 남쪽으로 이동하기 위해서는 2번의 회전이 필요하다.

그래프 알고리즘 문제 풀이 - 그래프 문제 카테고리

Github - https://github.com/hotehrud/acmicpc/tree/master/graph

static int[][] map = new int[101][101];
static int[] dx = { 1, -1, 0, 0 }; // 동 서 남 북
static int[] dy = { 0, 0, 1, -1 };
static boolean[][][] c = new boolean[5][101][101];
static Robot start, end;
static int m, n;
 
private void solve() {
    m = sc.nextInt();
    n = sc.nextInt();
 
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            map[i][j] = sc.nextInt();
        }
    }
 
    int s = sc.nextInt();
    int e = sc.nextInt();
    int d = sc.nextInt();
 
    c[d][s][e] = true;
    start = new Robot(s, e, d, 0);
    end = new Robot(sc.nextInt(), sc.nextInt(), sc.nextInt(), 0);
 
    bfs();
}
 
public static void bfs() {
    Queue<Robot> q = new LinkedList<>();
    q.add(start);
 
    while (!q.isEmpty()) {
        Robot pos = q.poll();
        int d = pos.d;
        int cnt = pos.cnt;
        int y = pos.r;
        int x = pos.c;
 
        if (y == end.r && x == end.c && d == end.d) {
            System.out.println(cnt);
            return;
        }
 
        // 1, 2, 3 전진
        for (int i = 1; i <= 3; i++) {
            int nx = (dx[d - 1] * i) + x;
            int ny = (dy[d - 1] * i) + y;
 
            if (0 < nx && nx <= n && 0 < ny && ny <= m) {
                if (map[ny][nx] == 0) {
                    if (!c[d][ny][nx]) {
                        c[d][ny][nx] = true;
                        q.add(new Robot(ny, nx, d, cnt + 1));
                    }
                } else {
                    break;
                }
            }
        }
 
        // 회전
        for (int i = 1; i <= 4; i++) {
            if (d != i && !c[i][y][x]) {
                int add = 1;
                if (d == 1) {
                    if (i == 2) ++add;
                } else if (d == 2) {
                    if (i == 1) ++add;
                } else if (d == 3) {
                    if (i == 4) ++add;
                } else {
                    if (i == 3) ++add;
                }
                c[i][y][x] = true;
                q.add(new Robot(y, x, i, cnt + add));
            }
        }
    }
}
 
public static class Robot {
    int r;
    int c;
    int d;
    int cnt;
 
    Robot(int r, int c, int d, int cnt) {
        this.r = r;
        this.c = c;
        this.d = d;
        this.cnt = cnt;
    }
}