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

1600번: 말이 되고픈 원숭이

 

www.acmicpc.net

못가는 경우가 없는줄 알고 풀었다가 1번 틀렸다.. 문제를 꼼꼼히 읽자..

풀이

정말 조금 변형된 BFS이다. 4방향 탐색과 말처럼 이동할 수 있는 8방향 탐색을 해주면 된다.

코드

#include <iostream>
#include <queue>
using namespace std;

struct monkey {
    int x, y, cnt, k_cnt;
};

int k, w, h;
int map[201][201];
bool visited[201][201][31];
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };
const int h_dx[] = { 1, 2, 2, 1, -1, -2, -2, -1 }, h_dy[] = { -2, -1, 1, 2, 2, 1, -1, -2 };

int bfs() {
    queue<monkey> q;
    q.push({ 1, 1, 0, 0});
    visited[1][1][0] = true;

    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int cnt = q.front().cnt;
        int k_cnt = q.front().k_cnt;
        if (x == w && y == h) return cnt;
        q.pop();

        // 인접한 4방향 탐색
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 1 || nx > w || ny < 1 || ny > h || map[ny][nx] == true || visited[ny][nx][k_cnt] == true) continue;
            visited[ny][nx][k_cnt] = true;
            q.push({ nx, ny, cnt + 1, k_cnt });
        }

        // k번만큼 다 이동한 경우에는 인접한 4방향으로만 이동
        if (k_cnt == k) continue;

        // 말처럼 이동할 수 있는지 탐색
        for (int i = 0; i < 8; i++) {
            int nx = x + h_dx[i];
            int ny = y + h_dy[i];
            if (nx < 1 || nx > w || ny < 1 || ny > h || map[ny][nx] == true || visited[ny][nx][k_cnt+1] == true) continue;
            visited[ny][nx][k_cnt+1] = true;
            q.push({ nx, ny, cnt + 1, k_cnt + 1 });
        }
    }
    return -1;
}

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

    cin >> k;
    cin >> w >> h;
    for (int i = 1; i <= h; i++) 
        for (int j = 1; j <= w; j++)
            cin >> map[i][j];
    cout << bfs() << '\n';
    return 0;
}