백준 1726번 로봇[C++]

1. 문제 풀이

 너비우선탐색을 응용한 시뮬레이션 문제입니다. 동서남북에 대한 식별 번호들이 문제 설명에 주어져있습니다. 이로 인해 방향을 전환하는 명령어 수행에 어려움이 있을 수 있습니다. 따라서 초반에 주어진 입력된 방향값만 조정하여 풀이하는 것이 가장 깔끔한 풀이일 것 같습니다. 저는 문제에서 주어진 방향에 대한 식별 번호를 그대로 가져와 처리하느라 조금 시간이 소요되었습니다. 이외 주의할 점은 회전에 대해서도 가중치를 주어야 하는 점 밖에 없습니다.

 

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

// 동, 서, 남, 북
const int dx[4] = { 0, 0, 1, -1 };
const int dy[4] = { 1, -1, 0, 0 };

int n, m;
bool board[105][105];

queue<ti> q; // { dir, x, y }
int d[4][105][105];

int sd, sx, sy;
int ed, ex, ey;

bool OOB(int x, int y) {
    return x < 0 or x >= n or y < 0 or y >= m;
}

pi go_k(int cx, int cy, int dir, int k) {
    return { cx + dx[dir] * k, cy + dy[dir] * k };
}

int turn(int dir, int offset) {
    return ((dir >> 1 << 1) + offset) % 4;
}

int main() {
    fastio(nullptr, false);

    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> board[i][j];
        }
    }
    
    cin >> sx >> sy >> sd;
    cin >> ex >> ey >> ed;

    sd--, sx--, sy--;
    ed--, ex--, ey--;

    memset(d, -1, sizeof(d));

    d[sd][sx][sy] = 0;
    q.push({sd, sx, sy});
    while(sz(q)) {
        auto [cd, cx, cy] = q.front(); q.pop();
        // first command : Go k
        for(int k = 1; k <= 3; k++) {
            auto [nx, ny] = go_k(cx, cy, cd, k);
            if(OOB(nx, ny) || board[nx][ny]) break;
            if(d[cd][nx][ny] != -1 && d[cd][nx][ny] <= d[cd][cx][cy] + 1) continue;
            d[cd][nx][ny] = d[cd][cx][cy] + 1;
            q.push({cd, nx, ny});
        }

        // second command : turn
        for(int offset = 2; offset <= 3; offset++) {
            int nd = turn(cd, offset);
            if(d[nd][cx][cy] != -1 && d[nd][cx][cy] <= d[cd][cx][cy] + 1) continue;
            d[nd][cx][cy] = d[cd][cx][cy] + 1;
            q.push({nd, cx, cy});
        }
    }

    cout << d[ed][ex][ey];
}

 

3. 제출 결과