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

문제 링크: https://www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

<문제 풀이> BFS

 

어떤 위치에 도달했을 때 지금까지 말처럼 몇 번을 이동해서 왔는지를 좌표와 함께 저장하는 클래스를 두고

BFS를 돌리면 되는데  다음 좌표인 nx, ny에 도달했을 때 방문 체크를 k개를 해야 합니다.

nx, ny까지 말처럼 이동한 횟수가 0일 때

nx, ny까지 말처럼 이동한 횟수가 1일 때

                   .

                   .

nx, ny까지 말처럼 이동한 횟수가 k일 때

 

 

그리고 현재 좌표인 cx, cy에서 지금까지 말처럼 이동한 횟수가 k보다 작을 경우엔

나이트 이동 방향 8개 + 동서남북 4방향을 push 하고

k보다 크거나 같은 경우엔 동서남북 4방향만 push 하면 됩니다.

 

말이 목적지에 도착하면

 

말처럼 0번 이동해서 올 경우

말처럼 1번 이동해서 올 경우

                  .

                  .

말처럼 k번 이동해서 올 경우

k + 1가지 경우의 최솟값을 return 하면 됩니다.

 

 

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
using namespace std;
 
#define X first 
#define Y second 
 
int h_dx[8] = { -2 ,-1, 1, 2, -2, -1, 1, 2 };
int h_dy[8] = { -1 ,-2, -2, -1, 1, 2, 2, 1 };
int dx[4] = { 0,-1, 0 , 1 };
int dy[4] = { 1, 0, -1 , 0 };
int board[200][200];
int visited[200][200][31];
 
int k, w, h;
int res = INT_MAX;
class pos {
public:
    int x;
    int y;
    int t; //말처럼 이동한 횟수
    pos(int x, int y, int t) : x(x), y(y), t(t) {
    }
};
 
int bfs() {
    queue<pos> Q;
    Q.push({ 0, 0, 0 });
    visited[0][0][0] = 1;
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        if (cur.x == h - 1 && cur.y == w - 1) { // 목적지에 도착
            for (int i = 0; i <= 30; i++) {
                if (visited[cur.x][cur.y][i]) {
                    res = min(res, visited[cur.x][cur.y][i]);
                }
            }
            return res - 1;
        }
        if (cur.t < k) {
            for (int dir = 0; dir < 8; dir++) {
                int nx = cur.x + h_dx[dir];
                int ny = cur.y + h_dy[dir];
                if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
                if (board[nx][ny] == 1 || visited[nx][ny][cur.t + 1]) continue;
                Q.push({ nx, ny, cur.t + 1 });
                visited[nx][ny][cur.t + 1] = visited[cur.x][cur.y][cur.t] + 1;
            }
 
        }
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.x + dx[dir];
            int ny = cur.y + dy[dir];
            if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
            if (board[nx][ny] == 1 || visited[nx][ny][cur.t]) continue;
     
            Q.push({ nx, ny, cur.t });
            visited[nx][ny][cur.t] = visited[cur.x][cur.y][cur.t] + 1;
 
        }
    }
    return -1; // 말이 목적지에 도착을 못함
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> k>>w >> h;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> board[i][j];
        }
    }
    cout << bfs();
 
    return 0;
}