[BOJ] 1600번 : 말이 되고픈 원숭이 (C++)

https://www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

 

구현 아이디어는 그리 어렵지 않게 생각해낼 수 있다.

 

1. (0,0)을 큐에 넣고 BFS를 돌린다. 

2. BFS를 돌릴 때 기본적인 BFS와 다른 점은 상하좌우 4방향에 대한 탐색뿐만 아니라 말이 이동가능한 8방향에 대해서도 탐색이 이뤄줘야 한다는 것이다. 

3. 벽부수고이동하기 문제처럼 3차원의 큐를 이용하여 말의 움직임을 몇 번 했는지를 체크하며, 말의 움직임이 k번보다 작을 때에만 말의 움직임에 대한 탐색을 한다.

 

추가로 dist 배열을 초기화하지 않으며 처음 시작하는 좌표의 거리값을 1로 두는 대신,

0으로 초기화되어 있는 상태를 이용하며 마지막에 답을 -1하여 출력한다.

 

 

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define X first
#define Y second

int k, h, w;
int area[202][202];
int dist[32][202][202]; //[k][x][y]:말움직임을 k번사용하여 x,y에 도착하는 최솟값
queue<pair<int,pair<int,int>>> q;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int cx[8]={1,2,2,1,-1,-2,-2,-1};
int cy[8]={-2,-1,1,2,2,1,-1,-2};

bool OOB(int x, int y){
    return x<0||x>=h||y<0||y>=w;
}

int BFS(){
    while(!q.empty()){
        auto cur = q.front(); q.pop();
        int curK = cur.X;
        int curX = cur.Y.X;
        int curY = cur.Y.Y;

        if(curX==h-1 && curY==w-1) return dist[curK][curX][curY]; //도착함
        //말의 움직임으로 가는 경우
        if(curK<k){ //k번 모두 했으면 더이상 할 수 없음
            for(int dir=0; dir<8; dir++){
                int nx = curX+cx[dir];
                int ny = curY+cy[dir];

                if(OOB(nx,ny)) continue;
                if(dist[curK+1][nx][ny] || area[nx][ny]) continue;
                
                dist[curK+1][nx][ny] = dist[curK][curX][curY]+1;
                q.push({curK+1,{nx,ny}});
            }
        }
        //원숭이의 움직임으로 가는 경우
        for(int dir=0; dir<4; dir++){
            int nx = curX+dx[dir];
            int ny = curY+dy[dir];

            if(OOB(nx,ny)) continue;
            if(dist[curK][nx][ny] || area[nx][ny]) continue;

            dist[curK][nx][ny] = dist[curK][curX][curY]+1;
            q.push({curK,{nx,ny}});
        }
        
    }

    return -1;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>k>>w>>h; //h가 행이고 w가 열

    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin>>area[i][j];
        }
    }

    //(0,0) 좌표 큐에 넣고 시작
    dist[0][0][0]=1; //-1로 초기화하는 대신 0으로 초기화된 상태를 이용하고 마지막에 -1을 해줌
    q.push({0,{0,0}});

    int ans = BFS();
    if(ans!=-1) cout<<ans-1;
    else cout<<-1;

    return 0;
}

 

참고로..... cx,cy라고 써야되는데  dx,dy가 익숙해서 말의 움직임에서 dx,dy로 써서 계속 OutOfBound가 났다.....

그런데 무섭게도 한 시간이 넘도록 찾을 수가 없었다......... ㅎ.... 겨우 찾음,, 습관의 무서움..