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

https://www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

• 도착점에 도착하는 최소 시간을 구하면 되므로 bfs를 사용하면 된다.
• 말의 움직임으로 움직일 수도 있고, 상하좌우로 움직일 수도 있다. 따라서 하나의 노드에 최소 시간으로 도착하는 경로는 여러 개일 수 있다. 예를 들어 (0, 0)에서 (1, 1)로 이동한다고 가정했을 때, 다음과 같이 2가지 방법으로 최소 시간으로 도착할 수 있다.
  • 상하좌우로만 움직였을 때: 2의 시간이 걸린다.
  • 말의 움직임 1번 + 상하좌우 1번으로 움직였을 때: 2의 시간이 걸린다.
• 즉, 하나의 노드에 도착할 수 있는 경우의 수는 여러 개가 존재할 수 있으며, 따라서 하나의 visited 배열만 두면 안된다. 따라서 말의 움직임을 n번 포함해서 움직였을 때를 각각의 경우로 나눠서 생각해야 한다. (int[][][] visited = new int[k + 1][h][w])
• 그리고 말의 움직임이 k번을 초과하는 경우에는 해당 움직임을 큐에 넣지 않고 버린다.
• 도착점에 도착한 경우, bfs이므로 가장 최초로 도착한 경우의 움직임이 답이 되고 반복문을 끝낸다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int answer;
    static int[] dx1 = {-2, -2, -1, -1, 1, 1, 2, 2};
    static int[] dy1 = {-1, 1, -2, 2, -2, 2, -1, 1};
    static int[] dx2 = {1, -1, 0, 0};
    static int[] dy2 = {0, 0, 1, -1};

    public static void main(String[] args) throws IOException {

        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[][][] visited = new int[k + 1][h][w];

        // bfs
        Queue<Node> que = new LinkedList<>();
        que.add(new Node(0, 0, 0));
        visited[0][0][0] = 1;

        while (!que.isEmpty()) {
            Node now = que.poll();
            if (now.x == w - 1 && now.y == h - 1) {
                answer = visited[now.kCnt][now.y][now.x];
                break;
            }

            // 말 이동 방식
            for (int i = 0; i < 8; i++) {
                if (now.kCnt + 1 > k) break;

                int nx = now.x + dx1[i];
                int ny = now.y + dy1[i];

                if (nx < 0 || nx >= w || ny < 0 || ny >= h) continue;

                if (map[ny][nx] == 0 && visited[now.kCnt + 1][ny][nx] == 0) {
                    que.add(new Node(ny, nx, now.kCnt + 1));
                    visited[now.kCnt + 1][ny][nx] = visited[now.kCnt][now.y][now.x] + 1;
                }
            }

            // 기본 이동 방식
            for (int i = 0; i < 4; i++) {
                int nx = now.x + dx2[i];
                int ny = now.y + dy2[i];

                if (nx < 0 || nx >= w || ny < 0 || ny >= h) continue;

                if (map[ny][nx] == 0 && visited[now.kCnt][ny][nx] == 0) {
                    que.add(new Node(ny, nx, now.kCnt));
                    visited[now.kCnt][ny][nx] = visited[now.kCnt][now.y][now.x] + 1;
                }
            }
        }
        answer = (answer == 0) ? -1 : --answer;
        System.out.println(answer);
    }

    public static class Node {
        int y, x;
        int kCnt;

        public Node(int y, int x, int kCnt) {
            this.y = y;
            this.x = x;
            this.kCnt = kCnt;
        }
    }
}