[BFS]백준1600번 말이 되고픈 원숭이

백준 1600번

말이 되고픈 원숭이

백준 문제 2206번, 벽 부수고 이동하기와 비슷한 문제였다.

하지만 벽 부수고 이동하기 문제는 벽을 부수고 이동할 수 있는 기회가 1번으로 고정되어 있었지만 이 문제의 경우는 말처럼 이동할 수 있는 기회가 최대 30번까지 입력으로 주어졌다.

말처럼 이동하기를 어느 위치에서 언제 사용하는지에 따라 최단 거리가 달라질 수 있다.

따라서 각 자리에서 말처럼 이동하기를 사용하는 경우의 수를 모두 고려해줘야 한다.

또한, 말처럼 이동하기를 사용할 수 있는 기회가 몇 번 남았는지에 따라서도 따로 관리를 해줘야 한다.

나의 경우 말처럼 이동하기를 사용할 수 있도록 주어진 기회의 횟수만큼 visited 배열을 따로 만들어서 관리했다.

처음에는 0번 배열에서 시작해, 말처럼 움직이기를 한 번 사용할 때마다 1번 배열, 2번 배열로 이동하게 하였다.

말처럼 이동한 경우의 좌표는 옆 배열에, 한 칸씩 움직인 경우(말처럼 이동하기를 사용하지 않은 경우)는 원래의 배열에서 이동할 수 있는 좌표를 찾도록 하였다.

BFS는 특정 좌표에 도착할 경우 가장 먼저 도착한 경우가 최단 거리임이 보장되기 때문에 어떤 배열이던 도착점에 도달하면 바로 거리를 출력하고 종료하면 된다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <tuple>
#include <string>

using namespace std;

vector<vector<int> > tmp(201,vector<int>(201,0));
vector<vector<int> >  map(201,vector<int>(201,0));
vector<vector<vector<bool> > > visited;
vector<vector<vector<int> > > level;
int horse_y_iter[8] = {1,1,-1,-1,2,2,-2,-2};
int horse_x_iter[8] = {2,-2,2,-2,1,-1,1,-1};
int y_iter[4] = {1,0,-1,0};
int x_iter[4] = {0,1,0,-1};
int main(){
    int horse, height, width;

    cin >> horse >> width >> height;
    for(int i=0;i<=horse;i++){
        vector<vector<bool> > arr(201,vector<bool>(201,false));
        visited.push_back(arr);
        level.push_back(tmp);
    }
    for(int i=0;i<height;i++){
        for(int j=0;j<width;j++){
            cin >> map[i][j];
        }
    }

    // chance y x level
    queue<tuple<int,int,int,int> > q; 
    q.push(make_tuple(0,0,0,0));
    visited[0][0][0] = true;
    
    while(!q.empty()){
        tuple<int,int,int,int> cur = q.front();
        q.pop();
        if(get<1>(cur) == height-1 && get<2>(cur) == width-1){
            cout << get<3>(cur) << endl;
            return 0;
        }

        if(get<0>(cur) < horse){ 
            for(int i=0;i<8;i++){
                int y = get<1>(cur) + horse_y_iter[i];
                int x = get<2>(cur) + horse_x_iter[i];
                int chance = get<0>(cur);
                int lev = get<3>(cur); 
                if(y>=0 && x >=0 && y<height && x <width){
                    //  cout << chance << " " <<  y << " " << x << endl;
                    if(map[y][x]==0 && (!visited[chance+1][y][x] ||(visited[chance+1][y][x] && level[chance+1][y][x]>lev+1))){
                        q.push(make_tuple(chance+1,y,x,lev+1));
                        visited[chance+1][y][x] = true;
                        level[chance+1][y][x] = lev+1;
                    }
                }
            }
        }
        
        for(int i=0;i<4;i++){
            int y = get<1>(cur) + y_iter[i];
            int x = get<2>(cur) + x_iter[i];
            int chance = get<0>(cur);
            int lev = get<3>(cur);
            if(y>=0 && x >=0 && y < height && x < width){
                if(map[y][x]==0 && (!visited[chance][y][x] || (visited[chance][y][x] && level[chance][y][x] > lev+1))){
                    q.push(make_tuple(chance,y,x,lev+1));
                    visited[chance][y][x] = true;
                    level[chance][y][x] = lev+1;
                }
            }
        }
    }
    cout << "-1" << endl;
    return 0;
}