[백준] 로봇

그래도 오랜만에 재미있는 BFS 문제를 풀어보았다. 솔직히 처음 읽자마자 아 이문제는 3차원 방문 벡터를 사용해야 되겠고 방향만 잘 읽으면은 문제 없이 풀 수 있겠다 싶었는데 너무 뜬금포인 부분에서 생각보다 시간을 너무 많이 소모해서 허탈하게 푼 문제다.

로봇이라는 객체가 받을 수 있는 명령은 2가지이다.

명령1 : 1, 2, 혹은 3까지 앞으로 나갈 수 있다.
명령2 : 현재 방향에서 Left 혹은 Right 방향으로 90도 꺾을 수 있다.

결국에 구현을 할때는 앞으로 3칸까지 가는 구현이랑 방향을 바꾸는 구현을 하면은 됐었다.

#include <iostream> 
#include <bits/stdc++.h> 
#define endl "\n"
#define MAX 100010
using namespace std;

int N,M; 
int matrix[101][101]; 
bool visited[101][101][4]; 
vector<pair<int,int>> dir = {{0,1},{0,-1},{1,0},{-1,0}}; //동 서 남 북 

struct Robot{
    int x, y, direction, dist; 
};

queue<Robot> q; 
vector<Robot> Goal; 

void Input(){
    cin >> N >> M; 
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> matrix[i][j]; 
        }
    }
    int x, y, dirr, goalX, goalY, goalDir;
    cin >> x >> y >> dirr >> goalX >> goalY >> goalDir; 
    q.push({--x,--y,--dirr,0}); 
    Goal.push_back({--goalX,--goalY,--goalDir}); 
}

pair<int,int> changeDir(int& curr_dir){
    if(curr_dir == 0 || curr_dir == 1){ //현재 방향이 동쪽 혹은 서쪽일때 
        return {3,2};
    }
    return {1,0}; 
}

bool check(int j,int x, int y, int curr_dir){
    for(int k = 1; k <= j; k++){
        int checkX = x + (dir[curr_dir].first * k);
        int checkY = y + (dir[curr_dir].second * k);
        if(matrix[checkX][checkY] == 1) return true; 
    }
    return false; 
}

void Solution(){
    Robot goal = Goal[0]; 
    //memset(visited,false,sizeof(visited)); 
    while(!q.empty()){
        int size = q.size();
        for(int i = 0; i < size; i++){
            Robot first = q.front();
            q.pop();

            int x = first.x, y = first.y, curr_dir = first.direction, curr_dist = first.dist; 

            if(x == goal.x && y == goal.y && curr_dir == goal.direction){
                cout << curr_dist << ' '; 
                return; 
            }

            for(int j = 1; j <= 3; j++){ //명령1 : 1 혹은 2 혹은 3칸까지 해당 방향으로 전진 할 수 있다. 
                int nX = x + (dir[curr_dir].first * j); 
                int nY = y + (dir[curr_dir].second * j); 

                if(nX < 0 || nY < 0 || nX >= N || nY >= M || check(j,x,y,curr_dir) || visited[nX][nY][curr_dir]) continue; 

                q.push({nX,nY,curr_dir,curr_dist+1}); 
                visited[nX][nY][curr_dir] = true; 
            }

            pair<int,int> result = changeDir(curr_dir); //명령2 : 방향을 90도로 왼쪽이나 오른쪽으로 바꿀 수 있다. 
            
            if(!visited[x][y][result.first]){
                q.push({x,y,result.first,curr_dist+1}); 
                visited[x][y][result.first] = true; 
            }
            if(!visited[x][y][result.second]){
                q.push({x,y,result.second,curr_dist+1}); 
                visited[x][y][result.second] = true; 
            }
            
        }
    }
}


void Solve(){
    Input();
    Solution(); 
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt", "r", stdin);
    Solve();
    return 0;

}

여기서 실수 했던 점은 명령1 에서 3칸까지 앞으로 갈 수 있는데 nX 와 nY 를 설정 해줄때 곱하기로 계산 하면 편한것을 난 억지로 더하기로 계산을 해주었다. 그리고 일반적으로 matrix[nX][nY] 가 1일 경우를 쓰는게 아니고 3칸을 앞으로 가는 명령을 했을때도 만약 이 전칸이 1이면은 통과를 못하기에 그 부분을 check() 으로 잡아주었다.

그리고 마지막으로 실수 한 점은 방향을 바꾸면서 q 에 집어 넣을때 내가 방문 체크를 안해줬어서 메모리 초과가 처음에 났었다.

배운점:
1. q 에 넣을때는 언제나 방문 체크 잊지 말자!
2. 구현을 할때 다양하게 생각해보자.