이번에 풀어본 문제는
백준 1600번 말이 되고픈 원숭이 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Monkey
{
    int x,y,k,cnt;

    public Monkey(int x, int y, int k, int cnt) {
        this.x = x;
        this.y = y;
        this.k = k;
        this.cnt = cnt;
    }
}
public class Main {
    static int W,H;
    static int [][] map;
    static boolean [][][] isVisited;
    static int [] dx = {-1, 1, 0, 0, -1, -2, -2, -1, 1, 2, 2, 1};
    static int [] dy = {0, 0, -1, 1, -2, -1, 1, 2, 2, 1, -1, -2};
    static Queue<Monkey> q;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int K = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        W = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        map = new int[H][W];
        isVisited = new boolean[H][W][K+1];

        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());
            }
        }

        q = new LinkedList<>();
        q.add(new Monkey(0,0,K,0));
        isVisited[0][0][K] = true;

        int answer = -1;
        while (!q.isEmpty()) {
            Monkey cur = q.poll();

            if(cur.x == H - 1 && cur.y == W - 1) {
                answer = cur.cnt;
                break;
            }
            //기본 움직임
            for (int idx = 0; idx < 4; idx++) {
                int mx = cur.x + dx[idx];
                int my = cur.y + dy[idx];

                if (isValid(mx,my,cur.k)) {
                    isVisited[mx][my][cur.k] = true;
                    q.add(new Monkey(mx, my, cur.k, cur.cnt + 1));
                }
            }
            // k가 양수면 말무빙
            if (cur.k > 0) {
                for(int idx = 4; idx < 12; idx++) {
                    int mx = cur.x + dx[idx];
                    int my = cur.y + dy[idx];

                    if (isValid(mx,my,cur.k - 1)) {
                        isVisited[mx][my][cur.k - 1] = true;
                        q.add(new Monkey(mx, my, cur.k - 1, cur.cnt + 1));
                    }
                }
            }
        }
        System.out.print(answer);
    }

    static boolean isValid(int x, int y,int k) {
        return x >= 0 && y >= 0 && x < H && y < W && !isVisited[x][y][k] && map[x][y] < 1;
    }
}

📝 풀이

K번 말처럼 움직일 수 있고, 일반적으로는 상하좌우로만 움직이는 원숭이가 출발지점(0,0) 에서 도착지점(H-1,W-1) 까지 도달할 수 있는 최소 이동값을 구하는 문제입니다.
그래프 탐색으로 쉽게 풀 수 있는 문제지만, 말처럼 이동할 수 있는 횟수가 K번으로 제한되어 있으므로 방문배열을 3차원으로 정의하여 처리해 주었습니다.

📜 후기

오랜만에 풀었더니..... 인덱스 값 잘못쓴거 못찾고 30분을 버렸습니다 ^^^^
따로 공부할게 생겨서 알고리즘에 소홀했는데, 앞으로는 꾸준히 풀어서 감을 찾아야겠네요ㅠㅠㅠㅠ