[BOJ] 백준 1726 로봇

문제 링크

https://www.acmicpc.net/problem/1726

1726번: 로봇

 

풀이

로봇의 위치와 방향을 묶어 하나의 스테이트로 저장해서 BFS를 돌리면 됩니다.

한 스테이트에서 갈 수 있는 경우의 수는 앞으로 1, 2, 3칸 전진, 왼쪽 회전, 오른쪽 회전입니다.

 

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ft first
#define sd second
 
int n, m, p[202][202];
// 0: east, 1: west, 2: south, 3: north
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int right_dir[] = {2, 3, 1, 0};
int left_dir[] = {3, 2, 0, 1};
tuple<int, int, int> st, ed;
bool isLegal(int x, int y){
    return (0 < x && x < n+1 && 0 < y && y < m+1 && p[x][y] == 0);
}
int bfs(){
    bool chk[200][200][4] = {0,};
    queue<tuple<int, int, int>> q;
    int x, y, dir;
    tie(x, y, dir) = st;
    chk[x][y][dir] = true;
    q.push(st);
    
    int lev = -1;
    while(!q.empty()){
        ++lev;
        int qsze = q.size();
        while(qsze--){
            if(q.front() == ed) return lev;
            tie(x, y, dir) = q.front();
            q.pop();
            
            for(int k=1; k<4; k++){
                int nx = x+dx[dir]*k;
                int ny = y+dy[dir]*k;
                if(!isLegal(nx, ny)) break;
                if(!chk[nx][ny][dir]) chk[nx][ny][dir] = true, q.push({nx, ny, dir});
            }
            int rdir = right_dir[dir];
            int ldir = left_dir[dir];
            if(!chk[x][y][rdir]) chk[x][y][rdir]=true, q.push({x, y, rdir});
            if(!chk[x][y][ldir]) chk[x][y][ldir]=true, q.push({x, y, ldir});
        }
    }
    return -1;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin>>n>>m;
    for(int i=1; i<n+1; i++){
        for(int j=1; j<m+1; j++){
            cin>>p[i][j];
        }
    }
    int x, y, z;
    cin>>x>>y>>z;
    st = {x, y, z-1};
    cin>>x>>y>>z;
    ed = {x, y, z-1};
    
    cout<<bfs();
}