[BaekJoon] 1600번 - 말이 되고픈 원숭이 [Java][C++]

문제 링크

---

1. 문제 풀이

원숭이는 기본적으로 상하좌우로만 움직일 수 있지만 최대 $K$ 번은 말처럼 움직일 수 있다. 최단 거리 BFS를 통해 해결할 수 있는데 이때 특정 좌표를 단순히 방문하는 것만 체크하는게 아니라 말처럼 몇 번 움직여서 방문했는지를 체크하면 두 움직임을 조합한 최단 거리를 구할 수 있다. 이를 위해 3차원 배열로 방문 체크를 만들어서 말처럼 움직일 수 있는 횟수가 남아 있으면 이 이동 방식도 큐에 삽입하는 방식으로 해결했다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {

    static final int[] dr = {-1, 0, 1, 0};
    static final int[] dc = {0, 1, 0, -1};
    static final int[] drh = {-1, -2, -2, -1, 1, 2, 2, 1};
    static final int[] dch = {-2, -1, 1, 2, 2, 1, -1, -2};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int K = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine());
        int W = Integer.parseInt(st.nextToken());
        int H = Integer.parseInt(st.nextToken());

        int[][] map = new int[H][W];
        for (int i = 0; i < H; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < W; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int result = bfs(K, H, W, map);
        System.out.println(result);
    }

    static int bfs(int K, int H, int W, int[][] map) {
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{0, 0, 0});

        boolean[][][] visited = new boolean[H][W][1 + K];
        visited[0][0][0] = true;

        int dist = 0;

        while (!q.isEmpty()) {
            int size = q.size();

            while (size-- > 0) {
                int[] node = q.poll();
                if (node[0] == H - 1 && node[1] == W - 1) return dist;

                for (int d = 0; d < 4; d++) {
                    int nr = node[0] + dr[d];
                    int nc = node[1] + dc[d];
                    int nk = node[2];

                    if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue;
                    if (map[nr][nc] == 1 || visited[nr][nc][nk]) continue;

                    q.offer(new int[]{nr, nc, nk});
                    visited[nr][nc][nk] = true;
                }

                if (node[2] == K) continue;

                for (int d = 0; d < 8; d++) {
                    int nr = node[0] + drh[d];
                    int nc = node[1] + dch[d];
                    int nk = node[2] + 1;

                    if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue;
                    if (map[nr][nc] == 1 || visited[nr][nc][nk]) continue;

                    q.offer(new int[]{nr, nc, nk});
                    visited[nr][nc][nk] = true;
                }
            }

            dist++;
        }

        return -1;
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
int drh[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
int dch[8] = {-2, -1, 1, 2, 2, 1, -1, -2};

int k, h, w;
int grid[200][200];
bool visited[200][200][31];

struct Node {
    int r, c, t;
};

int bfs() {
    queue<Node> q;
    q.push({0, 0, 0});

    visited[0][0][0] = true;

    int dist = 0;

    while (!q.empty()) {
        int sz = q.size();

        while (sz--) {
            auto [r, c, t] = q.front();
            q.pop();

            if (r == h - 1 && c == w - 1) return dist;

            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d];
                int nc = c + dc[d];
                int nt = t;

                if (nr < 0 || nr >= h || nc < 0 || nc >= w) continue;
                if (grid[nr][nc] == 1 || visited[nr][nc][nt]) continue;

                q.push({nr, nc, nt});
                visited[nr][nc][nt] = true;
            }

            if (t == k) continue;

            for (int d = 0; d < 8; d++) {
                int nr = r + drh[d];
                int nc = c + dch[d];
                int nt = t + 1;

                if (nr < 0 || nr >= h || nc < 0 || nc >= w) continue;
                if (grid[nr][nc] == 1 || visited[nr][nc][nt]) continue;

                q.push({nr, nc, nt});
                visited[nr][nc][nt] = true;
            }
        }

        dist++;
    }

    return -1;
}

int main() {
    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 >> grid[i][j];
        }
    }

    int res = bfs();
    cout << res;
}

---