[ 백준 1726 ] 로봇 (C++)

백준의 로봇(1726) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 기본적인 BFS/DFS 문제이지만, 일반적인 문제와 달리 하나의 정점에서 어느 방향을 보고 있느냐에 따라서 해당 정점의

   의미가 달라지는 문제이다. 핵심부터 말하자면, 똑같은 (1,1)에서 동쪽으로 보고있냐 남쪽을 보고있냐에 따라 다르다는

   것이다. 즉, 이미 탐색한 정점을 체크해주는 배열을 3차원 배열을 사용해줘야한다.

   Visit[x좌표][y좌표][바라보고 있는 방향] 이렇게 !

  

2) 바라보고 있는 방향을 1)에서 읽어본 방식으로 체크해주자. 또 하나는, 인접한 상하좌우로 한 칸씩 이동하는 것이 아니라

   현재 바라보고 있는 방향에서 최소 1칸에서 최대 3칸까지 한번에 움직일 수 있다는 점이 다르다.

   이 부분만 신경써서 구현해준다면 일반적인 BFS/DFS에서 크게 다른점이 없을 것이고, 어렵지 않을 것이다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<queue>
 
#define endl "\n"
#define MAX 101
using namespace std;
 
int M, N;
int MAP[MAX][MAX];
bool Visit[MAX][MAX][5];
 
int dx[] = { 0, 0, 0, 1, - 1 };
int dy[] = { 0, 1, -1, 0, 0 };
 
vector<pair<pair<int, int>, int >> Start, End;
 
void Input()
{
    cin >> M >> N;
    for (int i = 1; i <= M; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            cin >> MAP[i][j];
        }
    }
    int a, b, c;
    cin >> a >> b >> c;
    Start.push_back(make_pair(make_pair(a, b), c));
    cin >> a >> b >> c;
    End.push_back(make_pair(make_pair(a, b), c));
}
 
bool Can_Go(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 > M || ny > N) return false;
 
    nx = x;
    ny = y;
 
    for (int i = 0; i < k; i++)
    {
        nx = nx + dx[d];
        ny = ny + dy[d];
 
        if (MAP[nx][ny] == 1) return false;
    }
    return true;
}
 
int Change_Direction(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;
    }
}
 
void BFS(int a, int b, int c)
{
    queue < pair<pair<int, int>, pair<int, int>>> Q;
    Q.push(make_pair(make_pair(a, b), make_pair(c, 0)));
    Visit[a][b][c] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int d = Q.front().second.first;
        int Cnt = Q.front().second.second;
        Q.pop();
 
        if (x == End.front().first.first && y == End.front().first.second && d == End.front().second)
        {
            cout << Cnt << endl;
            return;
        }
 
        for (int i = 1; i <= 3; i++)
        {
            if (Can_Go(x, y, d, i) == true)
            {
                int nx = x + dx[d] * i;
                int ny = y + dy[d] * i;
 
                if (Visit[nx][ny][d] == false)
                {
                    Visit[nx][ny][d] = true;
                    Q.push(make_pair(make_pair(nx, ny), make_pair(d, Cnt + 1)));
                }
            }
        }
 
        int nd;
        nd = Change_Direction(d, 'L');
        if (Visit[x][y][nd] == false)
        {
            Visit[x][y][nd] = true;
            Q.push(make_pair(make_pair(x, y), make_pair(nd, Cnt + 1)));
        }
 
        nd = Change_Direction(d, 'R');
        if (Visit[x][y][nd] == false)
        {
            Visit[x][y][nd] = true;
            Q.push(make_pair(make_pair(x, y), make_pair(nd, Cnt + 1)));
        }
    }
}
 
void Solution()
{
    int x = Start.front().first.first;
    int y = Start.front().first.second;
    int d = Start.front().second;
    BFS(x, y, d);
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}