BOJ 1600 · 말이 되고픈 원숭이

알고리즘 분류 : BFS  

원숭이가 시작 지점(0, 0)에서 도착 지점(H-1, W-1)까지 이동하는데 걸리는 최단 거리를 구하는 문제다. 전형적인 BFS 문제이지만, 이동하는 방법이 조금 다르다. 14442번 '벽 부수고 이동하기 2'와 7562번 '나이트의 이동'에서 써먹은 테크닉을 적절히 사용하면 해결할 수 있다.

• 방문 체크와 이동 거리를 저장할 dist 배열을 3차원으로 선언한다.
• dist 배열의 인덱스는 [x 좌표] [y 좌표] [말 점프 횟수] 이다.
• Queue에도 x 좌표, y 좌표, 말 점프 횟수를 집어넣는다.
• 이동 방향을 정할 dx, dy 배열을 만든다.
• dx, dy의 배열 길이는 12이며, 앞에 4칸은 인접한 +1 이동이고, 뒤에 8칸은 말 점프 이동이다.
• 다음 이동을 정하는 for 문에서 인덱스 0~3 범위라면, 원숭이 이동이다. 즉 인접한 상하좌우 1칸만 이동한 것이다.
• 인덱스 4~11 범위라면, 말 점프 이동이다. 즉, 체스 나이트처럼 이동한 것이다.
• 말 점프를 사용할 때마다, 이를 카운트하고 큐에 집어넣으면서 BFS 탐색을 진행한다.
• 말 점프를 K 번만큼 모두 사용하면, for 문의 반복 범위를 4로 줄인다.
• (H-1, W-1)에 도착하면 BFS를 종료하고 이동 거리를 출력한다.

---

C++ 소스코드

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

struct monkey {
    int x, y, z;
};

int w, h, k;
int a[200][200];
int dist[200][200][31];
const int dx[] = {-1, 0, 1, 0, 2, 1, -1, -2, -2, -1, 1, 2};
const int dy[] = {0, 1, 0, -1, 1, 2, 2, 1, -1, -2, -2, -1};

void bfs() {
    queue<monkey> q;
    q.push({0, 0, 0});
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y, z = q.front().z; q.pop();
        int j = z == k ? 4 : 12;
        if (x == h-1 && y == w-1) {
            printf("%d\n", dist[x][y][z]);
            return;
        }
        for (int i=0; i<j; i++) {
            int nx = x+dx[i], ny = y+dy[i];
            int nz = i < 4 ? z : z+1;
            if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
            if (dist[nx][ny][nz] || a[nx][ny]) continue;
            dist[nx][ny][nz] = dist[x][y][z] + 1;
            q.push({nx, ny, nz});
        }
    }
    printf("-1\n");
}

int main() {
    scanf("%d", &k);
    scanf("%d %d", &w, &h);
    for (int i=0; i<h; i++) {
        for (int j=0; j<w; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    bfs();
    return 0;
}

---

Python 3 소스코드

from sys import stdin
from collections import deque
input = stdin.readline

dx = (-1, 0, 1, 0, 2, 1, -1, -2, -2, -1, 1, 2)
dy = (0, 1, 0, -1, 1, 2, 2, 1, -1, -2, -2, -1)
k = int(input())
w, h = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
d = [[[0]*(k+1) for _ in range(w)] for _ in range(h)]

def bfs():
    q = deque()
    q.append((0, 0, 0))
    while q:
        x, y, z = q.popleft()
        j = 4 if z == k else 12
        if x == h-1 and y == w-1:
            print(d[x][y][z])
            return
        for i in range(j):
            nx, ny = x+dx[i], y+dy[i]
            nz = z if i < 4 else z+1
            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                continue
            if not d[nx][ny][nz] and not a[nx][ny]:
                d[nx][ny][nz] = d[x][y][z]+1
                q.append((nx, ny, nz))
    print(-1)

bfs()

---

참고

• 백준 온라인 저지 : BOJ 1600
• 벽 부수고 이동하기
• 나이트의 이동