BOJ 1726 [로봇]

BOJ 로봇 : https://www.acmicpc.net/problem/1726

이번 문제는 백준 온라인 저지의 [로봇] 입니다.

재방문을 방지하기위해 Visited를 사용했습니다만, 

3차원으로 방향에 대한 방문도 고려하도록 했습니다.

로봇이 할 수 있는 행동인 1~3칸 앞으로 가기, 방향 꺾기 등을 큐에 담으며 탐색을 진행합니다.

#include <iostream>
#include <queue>
using namespace std;
int M, N;
int Map[100][100];
bool Visited[100][100][4];  //방향까지 봄
int d[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
class Node {
public:
    int i, j, dir, depth;
    Node() {}
    Node(int i, int j, int dir, int depth) : i(i), j(j), dir(dir), depth(depth) {}
};
queue<Node> q;
Node goal;
bool is_bound(int i, int j) {
    return i >= 0 && i < M && j >= 0 && j < N;
}
int BFS() {
    int result = 0;
    while(!q.empty()) {
        Node node = q.front();
        q.pop();
        int i = node.i;
        int j = node.j;
        int dir = node.dir;
        int depth = node.depth;
        if(i == goal.i && j == goal.j && dir == goal.dir) {
            return depth;
        }
        bool is_block = false;
        for(int k = 1; k <= 3; k++) {   //일직선으로 가기 먼저
            int next_i = i + d[dir][0] * k;
            int next_j = j + d[dir][1] * k;
            if(is_bound(next_i, next_j)) {
                if(!Map[next_i][next_j] && !Visited[next_i][next_j][dir]) {
                    Visited[next_i][next_j][dir] = true;
                    Node new_node(next_i, next_j, dir, depth + 1);
                    q.push(new_node);
                }
                else if(Map[next_i][next_j]){
                    is_block = true;
                }
            }
            if(is_block)
                break;
        }
        //회전 하기
        int next_dir_1, next_dir_2;
        if(dir == 0 || dir == 1) {
            next_dir_1 = 2;
            next_dir_2 = 3;
        }
        else {
            next_dir_1 = 0;
            next_dir_2 = 1;
        }
        if(!Visited[i][j][next_dir_1]) {
            Visited[i][j][next_dir_1] = true;
            Node new_node(i, j, next_dir_1, depth+1);
            q.push(new_node);
        }
        if(!Visited[i][j][next_dir_2]) {
            Visited[i][j][next_dir_2] = true;
            Node new_node(i, j, next_dir_2, depth+1);
            q.push(new_node);
        }
    }
    return result;
}
int main() {
    cin >> M >> N;
    for(int i = 0; i < M; i++)
        for(int j = 0; j < N; j++)
            cin >> Map[i][j];
    int i, j, dir;
    cin >> i >> j >> dir;
    Node first_node(i-1, j-1, dir-1, 0);
    Visited[i-1][j-1][dir-1] = true;
    q.push(first_node);
    cin >> i >> j >> dir;
    goal.i = i-1;
    goal.j = j-1;
    goal.dir = dir-1;
    cout << BFS() << endl;
    
    return 0;
}