[백준/C++] 1600번 말이 되고픈 원숭이

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

1600번: 말이 되고픈 원숭이

이 문제는 단순 bfs + 약간의 구현이라고 생각한다. 16509번 장군 문제를 풀고 오시면 뭔가 비슷한데..? 라고 느끼실 수 있다.

그러나! 이 문제의 요점은 바로 원숭이가 말(馬)처럼 K번 움직일 수 있다는 것이다. 때문에 주의할 점이 2가지 존재한다.

1. 한 점에서 탐색을 할 때 말처럼 움직일 수 있으면 말처럼 움직이고, 상하좌우 탐색도 같이 해줘야한다는 것!

2. 아래 그림처럼 벽으로 막혀있지만, 말처럼 움직일 수 있는 기회가 남아있어서 벽을 지나갈 수 있는 예제를 보자. 이 경우 K가 1이라면 해당 기회를 신중히 잘 써야한다.

-> 각 정점의 정보를 큐에 넣을 때, {해당 정점의 좌표쌍} + {시작지점에서 해당 정점까지 움직인 횟수, 말처럼 움직일 수 있는 능력을 사용한 횟수 쌍}을 넣어주어 모든 경우의 수를 탐색하였다.

그러기 위해서 3차원 배열을 사용해야하는데, visited[x][y][z]를 이용했다. x는 x좌표를 의미하며, y는 y좌표를 의미한다.

z는 0~30까지의 값을 가지는데, 이 숫자는 해당 x,y좌표까지 오면서 사용한 능력의 횟수를 의미한다!

ex) visited[2][2][1]가 true라면 2,2로 오는데 1번의 능력을 사용했음을 의미한다.

boolean 타입이라 헷갈리면 int 타입을 이용하자! 이게 더 직관적일 것이다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <cstring>
#include <string>
#include <queue>
#include <functional>
#include <complex>
#include <cmath>
#include <unordered_map>
#include <map>
typedef long long ll;
using namespace std;

int k,w,h;
int board[210][210];
bool visited[210][210][31];

int dx[]={0,1,0,-1};
int dy[] = {1,0,-1,0};

int hx[] = {-2,-2,-1,1,2,2,1,-1};
int hy[] = {-1,1,2,2,1,-1,-2,-2};

void bfs(){
    // {x,y 좌표쌍} , {이동횟수 , 말처럼 이동한 횟수 쌍}
    queue<pair<pair<int,int>,pair<int,int>>>q;
    q.push({{0,0},{0,0}}); // start
    visited[0][0][0]=true;

    while(!q.empty()) {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int cnt = q.front().second.first;
        int able = q.front().second.second;
        q.pop();

        if (x == h - 1 && y == w - 1) {
            cout << cnt;
            return;
        }
        if (able < k) { // 말처럼 이동 가능하면
            for (int i = 0; i < 8; i++) {
                int nx = x + hx[i];
                int ny = y + hy[i];
                if (nx >= 0 & nx < h && ny >= 0 && ny < w && !visited[nx][ny][able + 1] && board[nx][ny] == 0) {
                    q.push({{nx, ny}, {cnt+1,able+1}});
                    visited[nx][ny][able+1] = true;
                }
            }
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 & nx < h && ny >= 0 && ny < w && !visited[nx][ny][able] && board[nx][ny] == 0) {
                q.push({{nx, ny}, {cnt+1,able}});
                visited[nx][ny][able] = true;
            }
        }
    }
    cout << -1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> k >> w >> h;

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