백준 1600번 [말이 되고픈 원숭이](C++) -yes6686- 티스토리

백준 문제 풀이: 1600 (말이 되고픈 원숭이)

---

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

문제 설명:

원숭이가 일반적인 상하좌우 4방향 이동 외에도, 최대 K번까지는 말처럼 L자 점프(8방향)를 할 수 있을 때, (0,0)에서 (w-1,h-1)로 이동하는 데 필요한 최소 이동 횟수를 구하는 문제입니다. 맵에는 장애물(1)이 있을 수 있고, 점프는 장애물을 넘을 수 없습니다. 이동 불가능한 경우 -1을 출력합니다.

---

문제 해결 코드

// 1600번: 말이 되고픈 원숭이
// 일반 이동 + 말 점프(BFS) with 3차원 visited 배열

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

int arr[201][201];               // 격자 정보
int visited[201][201][31];       // [x][y][k번 말점프 사용 여부]
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
int hx[8] = { -2, -1, 1, 2, -2, -1, 1, 2 };
int hy[8] = { -1, -2, -2, -1, 1, 2, 2, 1 };

int minAns = 40001;
int w, h;

queue<pair<pair<int, int>, pair<int, int>>> q; // ((x, y), (총 이동횟수, 말점프 횟수))

void bfs(int x, int y, int k) {
    q.push({ {x, y}, {0, 0} });
    visited[x][y][0] = 1;

    while (!q.empty()) {
        auto [pos, state] = q.front(); q.pop();
        int kx = pos.first, ky = pos.second;
        int cnt = state.first, u = state.second;

        // 일반 4방향 이동
        for (int i = 0; i < 4; i++) {
            int nx = kx + dx[i];
            int ny = ky + dy[i];
            if (nx < 0 || ny < 0 || nx >= w || ny >= h) continue;
            if (arr[nx][ny] == 1 || visited[nx][ny][u]) continue;

            visited[nx][ny][u] = 1;
            if (nx == w - 1 && ny == h - 1) {
                minAns = min(minAns, cnt + 1);
                continue;
            }
            q.push({ {nx, ny}, {cnt + 1, u} });
        }

        // 말처럼 점프 (최대 k번까지 가능)
        if (u < k) {
            for (int i = 0; i < 8; i++) {
                int nx = kx + hx[i];
                int ny = ky + hy[i];
                if (nx < 0 || ny < 0 || nx >= w || ny >= h) continue;
                if (arr[nx][ny] == 1 || visited[nx][ny][u + 1]) continue;

                visited[nx][ny][u + 1] = 1;
                if (nx == w - 1 && ny == h - 1) {
                    minAns = min(minAns, cnt + 1);
                    continue;
                }
                q.push({ {nx, ny}, {cnt + 1, u + 1} });
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

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

    bfs(0, 0, k);

    if (h == 1 && w == 1) {
        cout << 0 << '\n';
    } else if (minAns == 40001) {
        cout << -1 << '\n';
    } else {
        cout << minAns << '\n';
    }
}

---

코드 설명

• 핵심 알고리즘: BFS + 3차원 visited 배열
• 상태 표현: (x, y) 위치 + 말 점프 횟수
• 중요 조건: 같은 칸이라도 점프 횟수가 다르면 다른 상태로 처리
• 도착 즉시 minAns 갱신

---

결과

(0,0)에서 (w-1,h-1)까지 최소 이동 횟수를 출력합니다. 도달 불가 시 -1 출력.

예시 입력:
1
4 4
0 0 0 0
1 0 0 0
0 0 1 0
0 1 0 0

예시 출력:
4

다른 접근 방식이나 개선 아이디어가 있다면 댓글로 공유해주세요!