BOJ : 1726 로봇

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

출처

Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2005 > 고등부 3번

명령어 go K의 의미를 잘못 해석해서 해맸었는데 결론은 총 다섯 가지 방법을 탐색하면 됩니다

go 1, go 2, go 3, 90도 회전 -90도 회전.

가장 중요한 것은 visited배열의 활용, 예외사항 판별, 실행 가능한 명령어 구분입니다.

1. 방향 구분없이 이동만 한다면 좌표에 해당되는 2차원 visited배열을 만들었겠지만 방향이 존재하기 때문에 방향에 따른 visited배열을 추가하여 3차원 배열 생성

2. 맵 이탈, 재방문, 궤도가 아닌 곳을 예외처리

3. go 1,2,3 / 90도, -90도 회전

먼저, 좌표와 방향, 그리고 명령어 횟수를 담는 Pos 클래스를 만들었습니다.

그리고 BFS를 이용하여 다섯가지 명령이 가능한지 판별하여 큐에 삽입.

#include <cstdio>
#include <queue>

using namespace std;

class Pos{
public:
    int r,c,dir,cnt=0;
    Pos(){};
    Pos(int _r, int _c, int _dir, int _cnt) : r(_r), c(_c), dir(_dir), cnt(_cnt){};
};

int N,M;
int map[102][102];
int pr[5] = {0, 0,0,1,-1};
int pc[5] = {0, 1,-1,0,0};
bool visited[102][102][5];
Pos st, en;
queue<Pos> q;

int opp(int n){
    if (n == 1)return 2;
    else if (n == 2)return 1;
    else if (n == 3)return 4;
    else return 3;
}

int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            scanf("%d",&map[i][j]);
    
    scanf("%d%d%d%d%d%d",&st.r, &st.c, &st.dir, &en.r, &en.c, &en.dir);
    
    q.push(st);
    visited[st.r][st.c][st.dir] = 1;
    
    while(!q.empty()){
        int r=q.front().r, c=q.front().c, dir=q.front().dir, cnt=q.front().cnt;
        q.pop();
        if(r == en.r && c == en.c && dir == en.dir){
            printf("%d\n",cnt);
            return 0;
        }
        
        int nr, nc;
        for(int i=1; i<=3; i++){
            nr = r + pr[dir] * i;
            nc = c + pc[dir] * i;
            if(nr <1  || nc < 1 || nr > N || nc > M) break;
            if(map[nr][nc]) break;
            if(visited[nr][nc][dir]) continue;
            visited[nr][nc][dir] = 1;
            q.push(Pos(nr,nc,dir,cnt+1));
        }
        
        for(int i=1; i<=4; i++){
            if(i == dir || i == opp(dir)) continue;
            if(visited[r][c][i]) continue;
            visited[r][c][i] = 1;
            q.push(Pos(r,c,i,cnt+1));
        }
    }
    return 0;
}