[백준] 1726_로봇 C++

12 May 2023 in Study on Coding Test

BFS를 사용해보는 문제

정답제출코드

#include <iostream>
#include <tuple>
#include <queue>
#include <cstring>

#define tuiii tuple<int, int, int>

using namespace std;

int M, N;
int map[101][101];
int StartX, StartY, StartDir;
int EndX, EndY, EndDir;
bool visited[101][101][5];
int Order[101][101][5];

int dx[5] = {0, 1, -1, 0, 0};
int dy[5] = {0, 0, 0, 1, -1};

bool CanGo(int x, int y, int d, int k)
{
    int nx = x + dx[d] * k;
    int ny = y + dy[d] * k;
 
    if (nx < 1 || ny < 1 || nx > N || ny > M)
        return false;
 
    nx = x;
    ny = y;
 
    for (int i = 0; i < k; i++)
    {
        nx = nx + dx[d];
        ny = ny + dy[d];
 
        if (map[ny][nx] == 1)
            return false;
    }
    return true;
}

int ChangeDir(int d, char c)
{
    if (c == 'L')
    {
        if (d == 1)
            return 4;
        else if (d == 2)
            return 3;
        else if (d == 3)
            return 1;
        else if (d == 4)
            return 2;
    }

    else if (c == 'R')
    {
        if (d == 1)
            return 3;
        else if (d == 2)
            return 4;
        else if (d == 3)
            return 2;
        else if (d == 4)
            return 1;
    }
}

int bfs(int X, int Y, int Dir)
{
    queue<tuiii> q;

    q.push({X, Y, Dir});
    visited[Y][X][Dir] = true;

    while (!q.empty())
    {
        int CurX = get<0>(q.front());
        int CurY = get<1>(q.front());
        int CurDir = get<2>(q.front());
        q.pop();

        if (CurX == EndX && CurY == EndY && CurDir == EndDir)
            break;

        for (int i = 1; i <= 3; ++i)
        {
            if (CanGo(CurX, CurY, CurDir, i))
            {
                int nx = CurX + dx[CurDir] * i;
                int ny = CurY + dy[CurDir] * i;

                if (!visited[ny][nx][CurDir])
                {
                    visited[ny][nx][CurDir] = true;
                    q.push({nx, ny, CurDir});
                    Order[ny][nx][CurDir] = Order[CurY][CurX][CurDir] + 1;
                }
            }
        }

        int nD;
        nD = ChangeDir(CurDir, 'L');
        if (!visited[CurY][CurX][nD])
        {
            visited[CurY][CurX][nD] = true;
            q.push({CurX, CurY, nD});
            Order[CurY][CurX][nD] = Order[CurY][CurX][CurDir] + 1;
        }

        nD = ChangeDir(CurDir, 'R');
        if (!visited[CurY][CurX][nD])
        {
            visited[CurY][CurX][nD] = true;
            q.push({CurX, CurY, nD});
            Order[CurY][CurX][nD] = Order[CurY][CurX][CurDir] + 1;
        }
    }
    
    return Order[EndY][EndX][EndDir];
}

int main()
{
    cin >> M >> N;

    for (int i = 1; i <= M; ++i)
    {
        for (int j = 1; j <= N; ++j)
            cin >> map[i][j];
    }

    cin >> StartY >> StartX >> StartDir;
    cin >> EndY >> EndX >> EndDir;

    memset(visited, false, sizeof(visited));
    memset(Order, 0, sizeof(Order));

    int ans = bfs(StartX, StartY, StartDir);

    cout << ans;

    return 0;
}

한 칸씩 이동하는 것이 아니라, 최대 세 칸까지 한 번에 이동하는 것이라서 고민을했다.

가다가 중간에 막히면 어떻게 명령을 저장할 지 고민을 많이 했던 것 같다.

기초적인 BFS를 짜고, Order의 수를 각 좌표와 방향별로 저장해야한다는 아이디어는 떠올렸지만

그 다음 과정이 생각나지 않아서 참고링크를 참고하여 풀었다.

BFS이기 때문에 최적경로가 나온다는 것은 변함이 없다.

명령을 내릴 때마다 Order의 배열에다가 새로운 값을 저장하도록 구현하였다.

그리고 Order 배열에서 도착지점의 원하는 방향에 있는 값이 출력되도록 마무리 하였다.

주의할 점은, 이번에는 동쪽 1, 서쪽 2, 남쪽 3, 북쪽 4 라는 방향이 정해져있기 때문에

dx, dy 배열을 만들 때 순서를 주의해야한다.