Problem 1600 - 말이 되고픈 원숭이(C++)

문제

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

1600번: 말이 되고픈 원숭이

 

풀이

미로탐색과 같은 일반적인 BFS 문제인데, 상하좌우가 아닌 다른 방향으로도 체크해봐야 하는 문제.

다른 방향(말의 움직임)을 체크하는 건 한도(K번)가 정해져있으므로, 그 한도도 같이 큐에 저장해서 풀었다.

 

큐에 값을 2개 넣는 건 해봤는데 3개 넣는 건 있는지도 몰랐다.

값을 2개 갖는 큐는 queue<pair<int,int>> q처럼 해주듯이

값을 3개 갖는 큐는 queue<tuple<int,int,int>> q 해주면 된다.

 

그리고 tuple을 사용할 때는 <tuple> 헤더를 추가해야 한다.

인텔리제이에서는 추가하지 않아도 컴파일 에러가 안 뜨길래 백준에 그대로 넣었는데,

백준에서는 컴파일 에러가 떠서 추가해 줬다.

 

맞는 거 같은데 도대체 왜 안되나 봤더니, 부등호 방향 잘못 써서,,,,,,,,,,,,,,,

이거 때문에 코드를 30분은 들여다본 듯.. ㅜㅜ

 

큐에 말의 움직임 한도를 같이 저장해야겠다는 생각이 들어서 그렇게 짜다가,

큐에 넣는 값이 하나 증가하니 이걸 어떻게 처리해야 할지 모르겠어서 다른 풀이를 참고해서 해결했다.

 

코드

#include <iostream>
#include <queue>
#include <tuple>
using namespace std;
int k,w,h;
int map[201][201];
int visited[201][201][31];
int dxm[4] = {-1,0,1,0}; // 원숭이의 움직임
int dym[4] = {0,1,0,-1};
int dxh[8] = {-2,-1,1,2,-2,-1,1,2}; // 말의 움직임
int dyh[8] = {1,2,2,1,-1,-2,-2,-1};

void bfs(int startx, int starty, int startk) {
    visited[startx][starty][startk]=1;
    queue<tuple<int,int,int>> q; // 큐에 좌표와 k를 함께 추가
    q.push({startx,starty,startk});

    while(!q.empty()) {
        int x = get<0>(q.front());
        int y = get<1>(q.front());
        int mk = get<2>(q.front());
        q.pop();
        if(x==h-1 && y==w-1) {
            cout<<visited[x][y][mk]-1;
            return;
        }
        if(mk!=0) { // 한도가 남았다면 말처럼 움직이는 경우를 큐에 추가
            for(int i=0; i<8; i++) {
                int rx = x+dxh[i];
                int ry = y+dyh[i];
                
                if(rx<0 || rx>=h || ry<0 || ry>= w) continue;
                
                if(!visited[rx][ry][mk-1] && map[rx][ry]==0) {
                    visited[rx][ry][mk-1] = visited[x][y][mk]+1;
                    q.push({rx,ry,mk-1});
                }
            }
        }
        for(int i=0; i<4; i++) { // 원숭이처럼 움직이는 경우를 큐에 추가
            int rx = x+dxm[i];
            int ry = y+dym[i];

            if(rx<0 || rx>=h || ry<0 || ry>= w) continue;

            if(!visited[rx][ry][mk] && map[rx][ry]==0) {
                visited[rx][ry][mk] = visited[x][y][mk]+1;
                q.push({rx,ry,mk});
            }
        }
    }
    cout<<"-1";
}

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

    bfs(0,0,k);
}