[C/C++] 백준 #1726 로봇(너비우선 탐색)

이번 문제는 복잡해 보이기는 하지만, 의미를 되새겨보면 마이크로 마우스 등에서도 사용할 수 있습니다.  실제 마이크로 마우스에서도 직진하는 경우에는 속도가 빠르기 때문에, 비슷하게 로직을 작성할 수가 있습니다.

 

문제는 로봇이 있는데, 현재 바라보는 방향이라면 최대 3칸까지 직진하는 명령을 줄 수 있습니다.  회전을 하는 것도 역시 명령을 줄 수 있는데, 이 때, 반시계 방향 또는 시계방향으로 90도 회전하라고 할 수 있습니다.

 

로봇이 움직일 공간 정보와 시작지점과 끝지점이 주어지면, 시작지점에서 끝지점까지 최소한의 명령어로 움직이게 하고싶습니다.  로봇은 동서남북 4방향으로만 바라볼 수 있고, 격자형태로 공간은 주어진다고 합니다.

 

아래 그림과 같이 로봇이 다닐 수 있는 길은 0의 값으로, 로봇이 갈 수 없는 곳은 1의 값이 주어질 때, 최소한의 명령어는 총 9번이 됩니다.

robot route

 

저는 기본적으로 너비 우선 탐색을 이용했습니다.  명령어 한번에 하나의 노드가 주어지는 것이죠.  그리고 이 문제는 현재 위치에서 로봇의 상태는 총 4가지가 됩니다.  동을 바라볼 수도 있고, 남을 바라볼 수도 있기때문에 바라보는 방향의 정보도 주어져야 합니다.

 

제가 이 부분은 하나의 int 값을 이용하기 비트를 나누어서 저장했습니다.  4개의 방향에는 2비트를 할당하면 됩니다.  가로와 세로 모두 100 이하의 수가 되므로, 7비트씩을 할당하면 상태의 각은 총 16비트이면 됩니다.

 

구조체의 비트 필드를 이용해도 되겠지만, 저는 직접 비트 조작을 해서 프로그램을 했습니다.

그리고 회전과 관련해서는 모듈러 연산을 했고요.  시계방향으로 돌 때에는 1을 더하고 4로 나눈 나머지를, 반시계방향으로 돌 때에는 3을 더하고 4로 나눈 나머지를 구했습니다.  C/C++ 언어는 모듈러 연산할 때 주의가 필요합니다.  음수의 모듈러 연산을 하면 음수가 나오기 때문이죠.  파이썬이라면 그런 걱정을 안 해도 되겠지만, 굳이 음수를 만들 필요가 없는 것이 다음과 같이 모듈러 4는 -1과 3이 같기 때문입니다.

 

\[ -1 \equiv 3 \mod ~ 4 \]

 

다음은 제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//---------------------------------------------------------------
//    baekjoon #1726 - Robot
//        - by Aubrey Choi
//        - created at 2019-07-14
//---------------------------------------------------------------
#include <stdio.h>
#include <queue>

//    EWSN, 1<=N,M<=100
int main()
{
    int n, m, s, t, r, c, d, start, end, dir[4] = {0, 2, 1, 3}, i, j, k;
    char map[100][100];
    std::queue<int> queue;
    scanf("%d%d", &n, &m);
    for(i = 0; i < n; i++) for(j = 0; j < m; j++)
    {
        scanf("%d", &s);
        map[i][j] = s?0x7f:0;
    }
    scanf("%d%d%d", &r, &c, &d);
    start = (r - 1) * 400 + (c - 1) * 4 + dir[d - 1];
    queue.push(start);
    map[r - 1][c - 1] |= 1 << dir[d - 1];
    scanf("%d%d%d", &r, &c, &d);
    end = (r - 1) * 400 + (c - 1) * 4 + dir[d - 1];
    for(;;)
    {
        s = queue.front(); queue.pop();
        t = s >> 16; s &= 0xffff;
        r = s / 400, c = (s / 4) % 100, d = s & 3;
        if(s == end) { printf("%d\n", t); break; }
        const int dxy[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
        for(k = 1; k <= 3; k++)
        {
            int nr = r + dxy[d][0]*k, nc = c + dxy[d][1]*k;
            if(nr < 0 || nr >= n || nc < 0 || nc >= m || map[nr][nc] == 0x7f) break;
            if(map[nr][nc] & (1 << d)) continue;
            int ns = nr * 400 + nc * 4 + d;
            queue.push(((t + 1) << 16) | ns);
            map[nr][nc] |= 1 << d;
        }
        int nd = (d + 1) % 4;
        if(!(map[r][c] & (1 << nd)))
        {
            int ns = (s & 0xfffc) | nd;
            queue.push(((t + 1) << 16) | ns);
            map[r][c] |= 1 << nd;
        }
        nd = (d + 3) % 4;
        if(!(map[r][c] & (1 << nd)))
        {
            int ns = (s & 0xfffc) | nd;
            queue.push(((t + 1) << 16) | ns);
            map[r][c] |= 1 << nd;
        }
    }
}