[백준 1726] 로봇

[백준 1726] 로봇

문제 링크

#include "header.h"
using namespace std;
int N, M;
int room[101][101];
int visit[101][101][5];
//1동 2서 3남 4북
int dx[5] = {0, 0, 0, 1, -1};
int dy[5] = {0, 1, -1, 0, 0};

typedef struct{
    int x;
    int y;
    int d;
    int cnt;
}st;
st robot;
st destination;

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

    int x, y, d;
    cin >> x >> y >> d;
    robot = {x, y, d, 0};

    cin >> x >> y >> d;
    destination = {x, y, d, 0};

}
int check(int x, int y){
    if((x == 1 || x == 2) && (y == 1 || y == 2)) return 1;
    if((x == 3 || x == 4) && (y == 3 || y == 4)) return 1;
    return 0;
}
void solve(){

    vector <int> candidate;
    queue <st> q;
    q.push(robot);
    visit[robot.x][robot.y][robot.d] = 1;

    while(!q.empty()){
        st top = q.front();
        q.pop();

        if(top.x == destination.x && top.y == destination.y && top.d == destination.d){
            cout <<  top.cnt << endl;
            return;
        }

        //top.d 방향으로 최대 3번 움직이기
        for(int j=1; j<=3; j++){
            int next_x = top.x + (dx[top.d] * j);
            int next_y = top.y + (dy[top.d] * j);
            if(visit[next_x][next_y][top.d]) continue;
            if(room[next_x][next_y] == 1|| next_x > N || next_y > M || next_x <= 0 || next_y <= 0) break;
            visit[next_x][next_y][top.d] = 1;
            q.push({next_x, next_y, top.d, top.cnt + 1}); //움직일 수 있다면 큐에 넣기
        }


        for(int i=1; i<=4; i++){
            if(i == top.d) continue;
            //다른 방향으로 움직이기            
            if(visit[top.x][top.y][i] || room[top.x][top.y] == 1 || top.x > N || top.y > M || top.x <= 0 || top.y <= 0) continue;
            
            if(check(top.d, i)){
                q.push({top.x, top.y, i, top.cnt + 2});
            }else{
                q.push({top.x, top.y, i, top.cnt + 1});
            }

            //해당 방향을 방문 처리 해 준다.
            visit[top.x][top.y][i] = 1;

        }
        
    }

}

int main(){

    input();
    solve();
    return 0;
}

• visit을 3차원 배열로 만들어서 x좌표, y좌표, 방향을 저장한다.
• bfs를 돌면서 top이 destination이라면 출력 후 종료한다.
• 아니라면
• 1. 최대 3칸 앞으로 갈 수 있는지 확인한다 (go)
• 1. 동서남북을 확인한다 (dir)
• 움직이는 go에서 +1씩 해주고,
• 동서남북을 확인하고 방향이 전환됨에 따라 +1, +2씩 해주면 된다.