백준 1600 말이 되고픈 원숭이

• 아이디어
  • BFS 활용하는 문제이다.
  • 벽 부수고 이동하기와 체스판 말 이동하기 문제를 합쳐놓은 듯하다.
  • 열, 행 순으로 주어진다.
  • 0,0부터 n-1,m-1까지 이동하는 최단 거리 출력한다.
  • 상하좌우와 체스판 말의 이동경우의 수 모두 고려
  • 도착지까지 갈 수 없으면 -1 출력

벽 부수고 이동하기 문제를 여러 복습한 덕에, 이러한 문제를 다시 만났을 때도 쉽게 해결할 수 있었다.

어려운 문제 또는 생소한 문제를 만나더라도 좌절하지 말고, 기뻐하며 복습하자. 나중에 이런 문제 나오면 쉽게 풀 수 있도록 말이다.

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int k, n, m;
int board[202][202];
int dist[202][202][32];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int hx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int hy[8] = {-1, -2, -2, -1, 1, 2, 2, 1};

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

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> k >> m >> n;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> board[i][j];
            fill(dist[i][j], dist[i][j]+31, -1);
        }
    }
    queue<tuple<int, int, int>> Q;
    Q.push({0, 0, 0});
    for(int i = 0; i < k; i++) {
        dist[0][0][i] = 0;
    }
    while(!Q.empty()) {
        int x, y, jump;
        tie(x, y, jump) = Q.front(); 
        if(x == n-1 && y == m-1) {
            cout << dist[x][y][jump];
            return 0;
        }
        Q.pop();
        int nextdist = dist[x][y][jump]+1;
        for(int dir = 0; dir < 4; dir++) {
            int nx = x+dx[dir];
            int ny = y+dy[dir];
            if(OOB(nx, ny)) continue;
            if(board[nx][ny] == 1 || dist[nx][ny][jump] != -1) continue;
            Q.push({nx, ny, jump});
            dist[nx][ny][jump] = nextdist;
        }
        if(jump < k) {
            jump++;
            for(int dir = 0; dir < 8; dir++) {
                int nx = x+hx[dir];
                int ny = y+hy[dir];
                if(OOB(nx, ny)) continue;
                if(board[nx][ny] == 1 || dist[nx][ny][jump] != -1 ) continue;
                dist[nx][ny][jump] = nextdist;
                Q.push({nx, ny, jump});
            }
        }
    }
    cout << -1;
    return 0;
}